Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Poupart, Pascal
Master of Science - MSc
University of British Columbia
Partially observable Markov decision processes (POMDPs) provide a principled approach to planning under uncertainty. Unfortunately, several sources of intractability currently limit the application of POMDPs to simple problems. The following thesis is concerned with one source of intractability in particular, namely the belief state monitoring task. As an agent executes a plan, it must track the state of the world by updating its beliefs with respect to the current state. Then, based on its current beliefs, the agent can look up the next action to execute in its plan. In many situations, an agent may be required to decide in real-time which action to execute next. Thus, efficient algorithms to update the current belief state would be desirable. Unfortunately, exact belief state monitoring turns out to be very time consuming for many domains. This thesis introduces a value-directed framework to analyze and design approximation methods that speed up the monitoring task. The goal of approximate belief state monitoring is to trade monitoring accuracy for efficiency. Thus, this framework outlines a principled approach to quantify the impact of approximating belief states on the original plan. Since at any point in time, an action is executed based on the current belief state, it may be possible that a less desirable action ends up being executed as a result of the approximations used to infer the current belief state. The framework developped covers a wide range of approximation methods including projection schemes and density trees. First, several bounds on the loss in decision quality due to approximate belief state monitoring are derived. Then, given a class of approximation methods, a few search algorithms are proposed to seek a relatively good approximation scheme within the given class. These algorithms essentially try to minimize the bounds derived. Next, a vector space analysis is performed to gain some insights regarding which properties of approximation methods are likely to ensure a minimal impact on decision quality. Finally, faster algorithms (than the previous ones) are designed to search for approximation methods that exhibit such properties.
5567790 bytes
application/pdf
Approximate Value-Directed Belief State Monitoring for Partially Observable Markov Decision Processes by Pascal Poupart B.Sc, McGill University, 1998 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Master of Science in T H E F A C U L T Y O F G R A D U A T E STUDIES (Department of Computer Science) We accen^Hris^thesis as) conforming required jjfcandard The University of British Columbia November 2000 © Pascal Poupart, 2000 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the Un i v e r s i t y of B r i t i s h Columbia, I agree that the Li b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r reference and study. I further agree that permission for extensive copying of t h i s thesis f o r s c h o l a r l y purposes may be granted by the head of my department or by his or her representatives. It i s understood that copying or p u b l i c a t i o n of t h i s thesis f o r f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of C O M P T E R S C I E N C E The U n i v e r s i t y of B r i t i s h Columbia Vancouver, Canada Date 2QQG>- 1\ ~TJ\ A b s t r a c t Partially observable Markov decision processes (POMDPs) provide a principled ap-proach to planning under uncertainty. Unfortunately, several sources of intractabil-ity currently limit the application of P O M D P s to simple problems. The following thesis is concerned with one source of intractability in particular, namely the belief state monitoring task. As an agent executes a plan, it must track the state of the world by updating its beliefs with respect to the current state. Then, based on its current beliefs, the agent can look up the next action to execute in its plan. In many situations, an agent may be required to decide in real-time which action to execute next. Thus, efficient algorithms to update the current belief state would be desirable. Unfortunately, exact belief state monitoring turns out to be very time consuming for many domains. This thesis introduces a value-directed framework to analyze and design ap-proximation methods that speed up the monitoring task. The goal of approximate belief state monitoring is to trade monitoring accuracy for efficiency. Thus, this framework outlines a principled approach to quantify the impact of approximating belief states on the original plan. Since at any point in time, an action is executed based on the current belief state, it may be possible that a less desirable action ends up being executed as a result of the approximations used to infer the current belief state. The framework developped covers a wide range of approximation methods including projection schemes and density trees. First, several bounds on the loss in decision quality due to approximate belief state monitoring are derived. Then, given a class of approximation methods, a few search algorithms are proposed to seek a relatively good approximation scheme within the given class. These algorithms essentially try to minimize the bounds derived. Next, a vector space analysis is per-formed to gain some insights regarding which properties of approximation methods are likely to ensure a minimal impact on decision quality. Finally, faster algorithms (than the previous ones) are designed to search for approximation methods that exhibit such properties. n C o n t e n t s Abstract ii Contents iii List of Tables vi List of Figures viii Acknowledgements x 1 Introduction 1 1.1 Problem statement 1 1.2 Illustrative Example 3 1.3 Contributions 4 1.4 Outline 6 2 Partially Observable Markov Decision Processes (POMDPs) 8 2.1 Model Description 9 2.1.1 State Space S . 10 2.1.2 Action space A 11 2.1.3 Transition function T 11 2.1.4 Observation space Z 12 2.1.5 Observation function Z 12 iii 2.1.6 Reward function R 13 2.1.7 Horizon h and discount factor 7 13 2.2 Policies 14 2.2.1 Definition 14 2.2.2 Evaluation 17 2.3 Solution Algorithms 19 2.3.1 Incremental Pruning 19 2.3.2 Policy Iteration 23 2.4 Performance issues 25 2.4.1 Sources of Intractability 26 2.4.2 Factored Representation 26 2.5 Belief State Monitoring 29 2.5.1 Motivation 29 2.5.2 Dynamic Bayesian Networks (DBNs) 31 2.5.3 Approximation Methods 33 2.6 Thesis Assumptions 37 3 Value-Directed Approximations 39 3.1 Plan switching 40 3.1.1 Switch set computations 41 3.1.2 Switch set error bounds 47 3.2 Alternative plans v 53 3.2.1 Alt-set computations 54 3.2.2 Alt-set error bounds 57 3.3 Value-directed search 60 3.3.1 Lattice of projection schemes 61 3.3.2 Greedy search 63 iv 4 Vector Space Analysis 68 4.1 Vector space formulation 69 4.2 Vector space switch test 72 4.3 Vector space search 80 5 Empirical Evaluation 83 5.1 Proof of Concept 84 5.2 Experiments 87 5.2.1 Search running time 89 5.2.2 Error bound evaluation 91 5.2.3 Search algorithm comparison 93 6 Conclusion 108 6.1 Summary 108 6.2 Future Framework Enhancements 109 Appendix A Basics of Vector Spaces 112 Appendix B Test Problems 115 B . l Coffee Delivery 116 B.2 Widget Production 118 B.3 Pavement Maintenance 122 Bibliography 128 v L i s t o f T a b l e s 2.1 LP-dominance test: vector a is dominated by H — {a} when x < 0. . 21 2.2 DP procedure 22 3.1 Switch test program to determine if there exists a belief state 6 such that the projection S leads to a switch from ai to ay. The variables are x and each component b(s) of the vector b representing a belief state, at, aj, a.{ and S are fixed and therefore yield the variable coefficients 44 3.2 LP-switch test for projection schemes. The variables are x and each component b(s) and b'(s) of the vectors 6 and b' representing belief states, ai, aj, a\ and M , are fixed and therefore yield the variable coefficients 45 3.3 ;4i£-set DP procedure 57 4.1 VS-switch test for projection schemes. The optimization program has a strictly positive objective function when there exists a belief state b € Rai such that S(b) 6 Raj and a non-positive objective function where there doesn't exists such a belief state 74 v i 4.2 Linear VS-switch test for projection schemes. This L P has a strictly and b' e Raj such that b(M) = b'(M) for all marginals M defined by projection S and a non-positive objective function when there doesn't exist such belief states 75 5.1 P O M D P specifications for the factory example 85 5.2 Comparison of different distance measures 87 5.3 Solution statistics for the three test problems 88 5.4 Search running time 89 5.5 Coffee problem: error bound comparisons at 15 stages to go 92 5.6 Widget problem: error bound comparisons at 15 stages to go . . . . 92 5.7 Pavement problem: error bound comparisons at 15 stages to go . . . 92 vii L i s t o f F i g u r e s 2.1 Tree representation of a three-step conditional plan 15 2.2 Recursive definition of a conditional plan 16 2.3 Geometric View of Value Function 18 2.4 Finite state controller for a simple P O M D P with two actions and two observations 24 2.5 D T and A D D example 27 2.6 Two-slice D B N 32 2.7 Unrolled D B N with no observation 34 2.8 Density tree approximation 37 3.1 Relevant belief states at stage k 41 3.2 Regions for each maximizing a-vector 42 3.3 The Switch Set Swk(a3) of a 3 43 3.4 Lower surface of anti-dominating vectors 56 3.5 Lattice of Projection Schemes 62 4.1 Solution space of possible exact belief states b 71 4.2 Belief space regions for each a-vector 74 5.1 D B N for the factory example 86 5.2 Coffee problem: comparison of the average cumulative error obtained by different search algorithms 96 viii 5.3 Widget problem: comparison of the average cumulative error ob-tained by different search algorithms 97 5.4 Pavement problem: comparison of the average cumulative error ob-tained by different search algorithms 98 5.5 Pavement problem: comparison of the average error due to a single approximation at each stage for different search algorithms 99 5.6 Coffee problem: comparison of the average cumulative number of switches for different search algorithms 101 5.7 Widget problem: comparison of the average cumulative number of switches for different search algorithms 102 5.8 Pavement problem: comparison of the average cumulative number of switches for different search algorithms 103 5.9 i?-bound search with LP-switch tests for the coffee problem: compar-ison of the average cumulative error when the search is restricted to projection schemes with marginals of at most 1, 2, or 3 variables. . . 105 5.10 Max VS search for the coffee problem: comparison of the average cumulative error when the search is restricted to projection schemes with marginals of at most 1, 2, or 3 variables. . 106 5.11 Sum VS search for the coffee problem: comparison of the average cumulative error when the search is restricted to projection schemes with marginals of at most 1, 2, or 3 variables 107 ix A c k n o w l e d g e m e n t s I would like to acknowledge the invaluable contribution of many people who have helped me directly or indirectly in the accomplishment of this work. First and foremost, my supervisor, Craig Boutilier, has played a key role in guiding my first steps in the world of research. Without his support and continuous advice, this work would not have been possible. Craig has been a mentor as well as a friend and his generous support is greatly appreciated. I am also indepted to David Poole and Bob Price for their constructive comments which contributed to the final form of this thesis. I would also like to thank Bob for the many interesting and helpful discussions on various topics related to this work. I am grateful to the Laboratory for Computational Intelligence at the Uni-versity of British Columbia for providing me with a stimulating environment to learn and carry out research. I also thank the department of computer science at the University of Toronto for their hospitality while visiting in the final year of my Master's degree. Finally, my special thanks go my parents who have provided me with a warm and stable environment in the early stages of my life. This work is in part the fruit of their love and their care which have contributed to shape the man I am today. P A S C A L P O U P A R T The University of British Columbia November 2000 x Chapter 1 I n t r o d u c t i o n 1.1 Problem statement Partially observable Markov decision processes (POMDPs) have received consid-erable attention as a framework for decision theoretic planning. Their generality allows one to model uncertainty in action effects, sensor observations and state of knowledge. They also allow the practitioner to find an optimal plan (that takes into account this uncertainty) with respect to one or several concurrent objectives. De-spite their attractiveness as a conceptual model, P O M D P s have limited applicability as they are intractable: • The offline search for a solution (optimal plan) to a P O M D P is often in-tractable [28, 30]. • The online execution of an optimal plan often requires belief state monitoring which can be itself intractable. This thesis focuses on the online problem, namely belief state monitoring. In this work, it is assumed that a policy (plan) is represented by a mapping from belief states (probability distributionsover the states of the world) to actions. When that is the case, the agent must update its current belief state at each time step in 1 order to know which action to execute next. Unfortunately, the belief state moni-toring task tends to be a computationally intensive process which is unacceptable in practice (especially for real-time applications). In short, a belief update requires the computation of a probability distribution over the whole state space. In most domains, the state space is large so this computation is prohibitively expensive. One of the main reasons why state spaces for certain problems are large is be-cause the states are defined by a large collection of features or random variables. For such problems, each state corresponds to a joint instantiation of those variables and, consequently, the number of states is exponential in the number of variables. This is a serious problem since with only a few dozens of variables the state space grows larger than the internal memory of most of today's personal computers. Therefore, a very common approach to perform belief monitoring is to try to reason at the vari-able level instead of the state level. Dynamic Bayesian Networks (DBNs) provide a way to do this by exploiting variable independencies. Unfortunately, as Boyen and Koller [3] have shown, most if not all the variables tend to become correlated over time for non-trivial problems and therefore belief inference remains intractable. Due to the lack of effective exact inference methods to tackle large state space problems, several researchers have investigated approximate methods. These include: • Sampling [37, 20] • Density Trees [26] • Projection [3] • Variational methods [21] These methods trade monitoring accuracy for monitoring efficiency. When an agent's estimate of the current belief state is inexact, it is possible that it will execute a different action than the one indicated by the exact belief state. As time passes, if the belief state is repeatedly approximated, then the sequence of actions 2 executed may be completely different than the one prescribed by the policy for the true underlying state. Hence, an important question for approximate monitoring methods is: how do approximations influence decision quality? In the literature, when an analysis of the approximation quality is performed, it is usually done by measuring some distance between the exact and approximate belief states instead of evaluating the expected total loss. This is because general dynamical systems free of any decision process are usually considered and the ab-sence of a decision process gives some freedom as for which metric to use when evaluating the error between the approximate and exact belief states. Common dis-tance measures that have been used include KL-divergence (a measure of entropy), L i , Li and L ^ . Although they are well-known distance measures with useful the-oretical properties, they do not translate easily in a meaningful measure of the loss in performance for an agent. In the presence of a decision process (i.e., POMDPs) , the decision maker is primarily interested in how much expected utility is lost due to approximations. Since the expected utility of a P O M D P policy is given by its corresponding value function, I propose in the following chapters a framework to carry out a value-directed analysis of approximation methods. 1.2 I l lustrat ive Examp le Let's illustrate the importance of a value-directed analysis with a simple factory problem. Imagine a process in which two parts are stamped from the same machine A. Each part may be faulty with a certain probability. Since the parts are stamped by the same machine, their fault probabilities are correlated. If the parts are faulty, subsequent processing on some machine B may induce a monetary loss to the factory. Therefore, a controller gets to decide whether to reject the parts or to continue their processing. In the event where the parts are processed individually by machine B, the decision to reject or process each part is independent and the correlation between 3 their fault probability can be ignored safely.1 One could devise an approximation method whereby the approximate belief state is the same as the exact belief state except that the correlation between fault probabilities is ignored. If the correlation is strong, the distance between the exact and approximate belief states may be great (from a KL-divergence, L\, L2 or point of view), but the factory won't suffer any loss. On the other hand, if the parts are processed jointly by machine B, the decision to reject or process the parts is influenced by the correlation between their fault probability. If the consequences for processing faulty parts are disastrous (e.g., explosion), then it may not be wise to ignore a weak correlation even if the distance measured by KL-divergence, Li, L2 or is small. 1.3 Contributions The main contribution of this thesis consists of a theoretical framework to analyze value-directed belief state approximation in POMDPs. The framework provides a novel view of approximation methods and their impact on decision quality. A general technique is proposed to derive bounds on the loss in expected return associated with a given approximation method. The key to those error bounds is the use of the value function as a distance measure. The bounds computed are then used to search for a good approximation scheme that minimizes the loss in expected utility. Algorithms to compute such bounds and to search within a class of approximation methods are proposed for projection schemes and density trees. Those algorithms are not restricted to projection schemes or density trees as they can be used for any "linear" approximation method. Unfortunately, these algorithms are computationally intensive: they require, in the worst quadratic increase in the solution time to solve a POMDP. As ^ h e decisions are independent assuming that the result of the decision for one part cannot be observed before the decision for the other part is made. 4 mentioned earlier, solving POMDPs is already intractable, so the applicability of those algorithms is limited to trivial problems. The running time can be consid-erably improved by introducing a vector space formulation of the approximation problem. This formulation allows us to search for a good approximation method in a time comparable to that of solving POMDPs. This makes the value-directed framework practical for problems that we are currently able to solve using state of the art solution algorithms. The price paid for this efficiency consists of looser bounds and consequently, the approximation schemes returned by those efficient search algorithms have lower performance guarantees. On the other hand, experi-ments suggests that in practice the expected loss in utility remains roughly the same on average. Another aspect of the vector space formulation is the novel view it provides for understanding how some approximation methods alter policies. A n important observation shows that the difference in utility for alternative courses of action varies more in some directions of the belief space than others. If we consider belief states as points in belief space, we can characterize an approximation by the direction of the vector corresponding to the difference between the exact and approximate belief points. Intuitively, approximations with directions where the difference in utility for executing alternative courses of action varies slowly are less likely to impact decisions and therefore are more accurate. The vector space formulation enables us to identify very quickly approximation schemes with such directions of higher accuracy. Finally, this analysis of approximation direction explains in part why KL-divergence, L i , L2 and LQO do not translate well in a measure of loss in expected total return. Roughly speaking, they are distance measures and they do not differentiate between equally distant approximations that have different directions. 5 1.4 Outline The core of this work resides in Chapters 3 and 4 where some algorithms to compute error bounds and to search for good approximation schemes are presented. The framework is introduced in Chapter 3 and the vector space formulation is presented in Chapter 4. A n outline of each chapter follows. Chapter 2 presents a review of the P O M D P model and introduces the nota-tion used throughout the thesis. The main approaches (value iteration and policy iteration) used to solve exactly POMDPs are summarized and the sources of in-tractability that prevent them from being used effectively are described. Next, dynamic Bayesian networks (DBNs) are introduced as a popular method for belief state monitoring and some explanations are provided concerning the complexity of belief inference using them. Among the different approximation methods for belief state estimation, projection schemes and density trees are detailed as they will be the focus of this framework. Projection schemes can be easily integrated to DBNs for a significant speed up whereas density trees simplify greatly the error bound analysis. Finally the assumptions made throughout this thesis are stated. Chapter 3 introduces the value-directed approximation (VDA) framework for belief state monitoring. There are two components to this framework: the first computes a bound on the loss in expected return for a given P O M D P and a given approximation method, and the second describes greedy search procedures to find a good approximation method within a certain class of methods (projection schemes or density trees) for a given P O M D P . Although the algorithms to compute the bounds and to conduct the searches are executed offline, they are computationally inten-sive. In fact their complexity is similar to, but worse than, the algorithms to solve POMDPs (value iteration or policy iteration) which are known to be intractable. To that effect, Chapter 4 proposes a more efficient approach based on a vector space formulation. Essentially, the running time of those algorithms is improved by loosening the error bounds. Moreover, the vector space formulation provides a 6 different viewpoint for analysing partial belief state monitoring. The emphasis is on the direction of an approximation and how its knowledge can be exploited efficiently to estimate the loss in expected utility. Chapter 5 describes some empirical results obtained by applying the methods developed in this framework. First, the factory example introduced in Section 1.2 is revisited with specific transition probabilities and reward functions. As a proof of concept, it is shown how for a specific prior, the choice of a projection scheme that minimizes KL-divergence, L\ or L2 norms yields a different choice than that prescribed by a value-directed approach. Following, several experiments are carried out on three test problems. They evaluate and compare the running time of the search algorithms, the quality of the error bounds and the average expected loss incurred in practice. Finally, Chapter 6 summarizes the contributions of this thesis and elaborates on future extensions to the framework. In particular, one goal of the author is to extend this work to value-directed sampling since sampling is one of the most popular and effective method for tracking dynamical systems. Another possibility consists in integrating this framework for value-directed approximations with the algorithms to solve POMDPs. Ultimately, when solving POMDPs , it would be nice to take into account the fact that monitoring will be approximate. This may lead to ways to solve P O M D P s in a bounded-optimal fashion. 7 Chapter 2 Par t i a l ly Observable M a r k o v Decision Processes ( P O M D P s ) The P O M D P concept was first introduced in the control theory and operations re-search communities [9, 1, 35, 31, 6, 29] as a framework to model stochastic dynamical systems and to make optimal decisions. This framework was later considered by the artificial intelligence community as a principled approach to do planning under un-certainty [4, 22]. Compared to other methods, P O M D P s have the advantage of a well-founded theory since they can be viewed as a special (continuous) case of the well-known Markov decision processes (MDPs) which are rooted in probability theory, decision theory and utility theory. In this chapter, an overview of the P O M D P framework is presented with an emphasis on the concepts that will recur throughout the thesis. For instance, the reader should pay attention to the notion of a conditional plan and its value function representation as an a-vector. These will be instrumental in defining the notion of plan switching when analyzing how the course of action gets modified by an approximation. The reader should also pay special attention to the incremental pruning algorithm. This will ease the understanding of the algorithms to bound error and to search for good approximation schemes presented in later chapters. 8 Finally, we describe dynamic Bayesian networks for exact belief inference, as well as projection schemes and density trees for approximate inference, as they will serve to illustrate the value-directed framework. This chapter also provides an overview of the sources of intractability when solving a P O M D P . Although these are not the focus of this work, they limit the type of experiments that can be carried out when testing the value-directed framework. On the other hand, the research community has made some progress on several fronts and I have tried to incorporate some of the techniques developed to speed up the solution of POMDPs. For instance, factored representations allow us to solve some P O M D P s with significantly larger state spaces than before [2, 18, 15]. They also allow us to improve the running time of the algorithms developed in this thesis. As mentioned earlier, the bounding algorithms and the search algorithms are similar to incremental pruning and therefore can benefit from the same type of speed up. Lastly, this chapter addresses an important question regarding when and why belief state monitoring is required. In the literature, there are two common representations for P O M D P policies: as a mapping from belief states to actions; and as a finite state controller. The latter representation doesn't require belief state monitoring at execution time. Thus, one might seek an algorithm (such as Hansen's policy iteration [13, 14]) that outputs a finite state automaton to circumvent the belief state monitoring problem altogether. I argue that policy iteration is not always suitable for modeling and efficiency reasons, and even when it is suitable, it may still be desirable to monitor belief states for explanatory purposes. 2.1 Model Description P O M D P s provide a nice framework to model uncertainty in a planning problem. They allow action effects and state observations to be modeled probabilistically. Formally, a P O M D P is described as a tuple {S,A,Z,T,Z,R,h,'y) where: 9 • S is the set of states of the world. • A is the set of actions the agent can execute. • Z is the set of observations the agent can experience. • T : S x A —>• A(5) is the s£a£e transition function describing the dynamics of the world. A(S) is the set of all probability distributions over the set S of states. We write T(s, a, s') to denote the probability of a transition to state s' given that it was in state s at the previous stage and that the agent executed action a. • Z : AxS —> A(Z) is the observation function. A(Z) is the set of all probability distributions over the set Z of observations. We write Z(a,s',z') to denote the probability with which the agent may experience observation z' given that it just executed action a and the world made a transition to state s'. • R : S x A —> Sft is the reward function. We write R(s, a) to denote the reward received by the agent when the world is in state s and the agent executes action a. • h is the planning horizon. • 7 is the discount factor. 2.1.1 State Space S The world is modeled by a set S of distinct states. In this thesis, S is assumed to be finite for computational purposes, but in general, the P O M D P framework allows countably many states [33]. At any point in time, the relevant features of the world are summarized by a state s 6 S. More precisely, the ith feature is represented by variable Xi which can be instantiated to any value in the (finite) domain T>i of Xi. Each state s corresponds to a joint instantiation of all the variables X\,X2, • • •, Xn 10 encoding the world's relevant features. Assuming a total of n variables, the num-ber of states in S is then exponential in n since S = T>\ x T>2 x . . . x Vn. Note that this exponential relation between variables and states will be responsible for the intractable size of a-vectors (Section 2.4) and the intractability of belief state monitoring (Section 2.5). 2.1.2 Action space A A n agent living in this world seeks to influence its state by executing actions from the set A (A is also assumed to be finite for computational reasons). Roughly speaking, the agent's goal is to choose actions that will influence the world in a way that desirable states are visited frequently. On the other hand, as opposed to classical planning, where actions are assumed to be deterministic, P O M D P s allow uncertainty to be modeled for action effects. From the agent's point of view, this means that the world has a certain probability of making a transition to any state in S as a result of an action execution. 2.1.3 Transition function T The stochastic nature of action effects is captured by the transition function T . Time is discretized in consecutive steps called time steps at which the agent gets to execute an action in A. Here it is assumed that any action in A can be attempted in any state of the world and at any time step. After each action, the world makes a transition to a new state, so that over time, the world goes through a sequence of states (so, si, • . . , S f , . . . ) where t denotes the time step index. Assuming the transition function is the same at every time step (i.e., the transition function is stationary), then T(s,a,s') = Pr(s'\s,a) denotes the probability that the world makes a transition to state s' when action a is executed in state s. This transition function also assumes the Markov property, namely that the next state st+i of the world depends only on the current state sj and the current action at, and is 11 independent of past history (past states and past actions). Pr{st+i\st,at,st-i,at-i,.. .,s0,a0) = Pr(st+i\st,a) (2.1) 2.1.4 Observation space Z After executing an action, the agent makes an observation z £ Z. This observation provides some information as to what state the world just made a transition to. In fully observable MDPs, Z = S and the agent knows exactly the current state. In partially observable MDPs, which is the focus of this thesis, Z differs from S. Ob-servations provide only partial information to the agent since the same observation may be experienced in several states. Therefore, the agent remains uncertain about the current state of the world and it is said to have only beliefs about the current state. Those beliefs are usually represented by a probability distribution b over the set >S of world states. We write b(s) to denote the probability of s when the agent has beliefs b. 2.1.5 Observation function Z Partial observability is modeled by the observation function Z. Assuming the observation function is the same at every time step (i.e., it is stationary), then Z(a, s',z') = Pr(z'\a,s') denotes the probability that the agent experiences obser-vation z' after executing action a and making a transition to state s'. The transition and observation functions can be used to update the current belief state at each time step. That is, using Bayes rule, one can infer bt+i from bt, at and zt+i as follows: In the above equations, the denominator is the normalizing constant K = J2s'^s^t(s)P'r(s'\s^at)Pr(zt+i\0't,s') that ensures that 6 is a probability distribu-tion. If we think of b as a row vector, we can rewrite Equation 2.2 in matrix notation bt+i(s') = T,S£S bt(s)Pr(s'\s, at)Pr(zt+i\at, s' K T,seSbt(s)T(s, at, s')Z(at, s ' , zt+i) K (2.2) (2.3) 12 by transforming the transition and observation functions into linear operators. De-fine Ma<z to be an |<S| x \S\ matrix such that MatZ(i,j) — T(si,a,Sj)Z(a,Sj,z) is the likelihood of the world to transition from state S j to state Sj when action a is executed and observation z is experienced. We can further decompose the matrix MajZ into a product of matrices MaMz. Ma is a transition matrix such that Ma(i,j) — T(si,a,Sj) and Mz is a diagonal observation matrix such that Mz(i,i) = Z(a,Si,z). In matrix notation, we can compute bt+i from 6t, at and zt+i as follows: 2.1.6 Reward function R The preferences of the agent are encoded in the reward function R. This function indicates how much utility R(s, a) is earned by an agent when the world is in state s and it executes some action a. The reward function is a powerful tool since it allows simple classical planning goals as well as complex concurrent goals to be modeled. The key to modeling concurrent goals is the use of utility theory which provides a common scale that allows an agent to combine multiple goals and to make rational tradeoffs with respect to those goals. 2.1.7 Horizon h and discount factor 7 In decision theory, the goal of an agent is to maximize the expected utility earned over some time frame. The horizon h defines this time frame by specifying the number of time steps the agent must plan for. The horizon can be finite or infinite. A discount factor 7 is also used to indicate how rewards earned at different time steps should be weighted. In general, the more delayed a reward is, the smaller will be its weight. Therefore, 7 is a constant between 0 and 1 indicating by how much (2.4) K hMatM, K (2.5) 13 a reward should be scaled down for every time step delay. Finally, expression 2.6 shows the expected total discounted reward that an agent seeks to maximize for a given horizon h and a given discount factor 7. Expression 2.7 is the equivalent in matrix notation assuming Ra is a column vector such that Ra(s) = R(s,a). h Expected total discounted reward = ^ 7* ^ bt{s)R(s, at) (2-6) h = zZlXRat (2.7) t=0 2.2 Policies 2.2.1 Definition Given a tuple (S,A,Z,T,Z,R,h^) specifying a P O M D P , an important question is: what action should an agent execute at each time step to maximize its expected total return? In order to answer this question, we define II to be the set of all policies 7r (action strategies) that an agent can execute. Roughly speaking, a policy is some strategy that dictates which action a to execute (at each time step) based on some information previously gathered. The relevant information available to the agent consists of the initial belief state 60 and the history (sequence) of actions and observations experienced so far (histt = (ao, z\, a\, Z2, • • •, a*-i, zt)). Hence, a policy 7r is a mapping from initial belief states and histories to actions. For a given initial belief state, a policy 7r can be represented by a tree cor-responding to a conditional plan /3. Figure 2.1 shows such a tree for a three-step conditional plan. A conditional plan is intuitively defined as a mapping from his-tories to actions. The execution of a conditional plan essentially consists of the traversal of its corresponding tree from the root to a leaf by interleaving action execution and observation gathering. After traversing a node and executing its cor-responding action a, the next action to execute is associated with the child node 1 For computational purposes, the infinite-horizon case considered in this thesis always assumes a discount factor smaller than 1. 14 determined by the branch labelled with the next observation z experienced by the agent. In general, we can define recursively fc-step conditional plans (3^ m terms of (k — l)-step conditional plans Pk-i- The idea is to define = (a,o"fc) as an action a followed by an observation strategy o^. In turn, an observation strategy o~k : Z —> Tfc_i is a mapping from observations to conditional plans of length k — 1 (Tfc-i is the set of all (k — l)-step conditional plans). Figure 2.2 shows the recursive definition of the conditional plan corresponding in Figure 2.1. Note that one-step conditional plans correspond to an action only (i.e., T i = A) since an observation strategy is unecessary. Unfortunately, as the number of steps increases, so does the number and the length of histories, and it is infeasible to represent a mapping over all such histories. Alternatively, it is possible to summarize histories by belief states which have a fixed-size finite representation (0(|«S|)). A belief state is a sufficient statistic that encodes all the necessary information from previous actions and observations for planning purposes. For instance, belief state bt summarizes the relevant information encoded by the initial belief state bo and the sequence of actions and observations up to time step t. bt = (bo,ao,zi,ai,Z2,...,at-i,zt) (2.8) 15 conditional plan Stages to go P = <a1,cr> 3 CT^Zj) = <a 2 , a,> = <<Li,oi> 2 a&) = <a4> a^ = <&5> = ^ = <^> 1 Figure 2.2: Recursive definition of a conditional plan Intuitively, this follows from the fact that the transition function T(bt-\, at-\, bt) Pr(bt\bt-i,at-i) depends only on the previous belief state bt-\ (due to the Markov property). Since bt-\ = (bo, ao, z\, a\, z%, • • •, at-2, zt-\), we can rewrite Expres-sion 2.8 recursively as follows: Expression 2.9 is not surprising since we had already derived Equation 2.4 which tells us how to update bt from &t_i, at-i and zt- This update equation is rewritten below for convenience. Thus we can also define a policy TT as mappings nt(b) (one mapping for each time step t) from belief states to actions. When the mappings nt(b) are the same for all time steps, we say that the policy is stationary and we simply write 7r(6). In practice, representing a policy as mappings from belief states to actions can be problematic because the belief space is an (|<S| — l)-dimensional continuous space. Fortunately, a key result by Sondik [34] allows us to circumvent this problem. The explanations regarding Sondik's solution are deferred to the next section after value functions are introduced. h = (bt-i,at-i,zt) (2.9) bt-iMa K at-i,zt 16 2.2.2 Evaluation Given the set of all policies LT, we need a mechanism to evaluate and compare policies. Each policy rr has a corresponding value function V* : A(5) —>• which is defined as a mapping from initial belief states to expected total reward. For a given initial belief state, the value returned is the expected sum of the discounted rewards earned at each time step as defined by Equation 2.10. Here irt(bt) is the action at prescribed by policy TT at time step t for belief state bt-h V"(b0) = ' £ 1 t b t R M b t ) (2.10) t=o We can use value functions to order policies. A decision theoretic agent prefers 7r to n' when Vv(b) > V*' (b) for all b G A(5). This preference ordering is a partial order because there are pairs of policies for which neither policy has a value function greater than the other one for all belief states. On the other hand, there always exists an optimal policy n* such that its value function V"7r dominates all other policies (Vn\b) > V*{b) V T T , & ) . As with policies, representing a value function can be problematic because its domain is an |<S|-dimensional continuous space corresponding to the belief space. Fortunately, a key result of Sondik [34] shows that optimal value functions for finite-horizon P O M D P s are piecewise-linear and convex (PWLC). The idea is that at any point in time during the execution of a policy, the actions prescribed for the remaining steps form a conditional plan. The value function of a conditional plan is constant for any world state. Since belief states represent probability distributions over the set of world states, the value function of a conditional plan at any belief state b is simply the weighted average (according to 6) of the value at each world state. Thus the value function V@(b) of a conditional plan j3 is linear with respect to b. This means that V@(b) can be represented by an |S|-dimensional vector ap such that V^(b) = J2s€S Hs)ap(s)- ^ w e consider ap as a column vector, then in matrix notation, V@(b) = b • ap. Furthermore, using the recursive definition of conditional 17 Optimal Value Function 0 ^ b(s) ^ 1 Belief Space Figure 2.3: Geometric View of Value Function plans, we can compute a-vectors recursively: For a finite horizon h, an optimal policy irh consists of the best conditional plans for each initial belief state. Although there are uncountably many belief states, the set of /i-step conditional plans T/j is finite and therefore an /i-step optimal value function can be represented by a finite collection of a-vectors. Figure 2.3 shows an optimal value function for a simple two-state P O M D P . The horizontal axis represents belief space and the vertical axis indicates the ex-pected total reward. Assuming the two world states are s and s, then a belief state is completely determined by the probability of s. Therefore, the horizontal axis rep-resents a continuum of belief states determined by the probability b(s). Each line in the graph is an a-vector which corresponds to the value function of a conditional plan (3 = (a, a) as defined in Equation 2.11. The upper surface of those cc-vectors is a piecewise-linear and convex (PWLC) function corresponding to the optimal value function. 18 In general, as shown by Sondik [34], optimal value functions for finite-horizon problems are P W L C and can be represented succinctly by a finite collection of a-vectors. As for infinite-horizon POMDPs, the optimal value function is convex but not necessarily piecewise-linear. On the other hand, there always exists a sequence of P W L C value functions that converge in the limit to the optimal value function. This has considerably influenced the design of algorithms to find optimal policies, since most of the algorithms restrict their search to the set of policies with P W L C value functions. 2.3 Solution Algorithms In the past 30 years, several algorithms have been proposed to solve POMDPs . We can distinguish value iteration algorithms and policy iteration algorithms. Value iteration algorithms indirectly compute an optimal policy by iteratively refining its value function, whereas policy iteration algorithms directly refine a policy until it is optimal. Below, the incremental pruning algorithm [38] is reviewed as it is the fastest known value iteration algorithm [5] for the class of polynomially action-output-bounded P O M D P s [27] (a class of tractable P O M D P s also reviewed below). Note as well that many aspects of this algorithm will be reused by the algorithms introduced for error bound computation and approximation search. Among the policy iteration algorithms, Hansen's algorithm [13, 14] is reviewed because it is conceptually simple (compared to Sondik's algorithm [35, 36]), it has been observed to outperform value iteration algorithms on several examples and it circumvents the need for belief state monitoring by computing policies represented by finite state controllers. 2.3.1 Incremental Pruning Incremental pruning was first introduced by Zhang and Liu [38] and then analyzed by Cassandra, Littman and Zhang [5] from a computational complexity point of 19 view. For finite-horizon POMDPs, this algorithm incrementally constructs a fc-step optimal policy irk by dynamic programming (DP). Given Vk~l, the optimal value function for k — 1 stages to go, Vk is computed in a greedy fashion as follows. Here bz denotes the belief state that follows b when action a is executed and observation z is experienced: Vk(b) = max bRa + ^Pr{z\b,a)Vk-1{baz) (2.12) Incremental pruning decomposes this DP backup (Equation 2.12) in three steps (Equations 2.13, 2.14 and 2.15). Two intermediary P W L C value functions (Vkz and Vk) are first computed and then the optimal value function (Vk) is computed. Roughly speaking, Vkz corresponds to the expected return of executing action a and making observation z followed by executing an optimal (k — l)-step policy nk~1, whereas Vk corresponds to the expected return of executing action a and making some unknown observation z, followed by executing an optimal (k — l)-step policy Vakz(b) = j ^ + lPr(z\b,a)Vk-l(baz) (2.13) Vak(b) = zZKM (2.14) Vk(b) = max Vk(b) (2.15) Using Sondik's observation that P W L C value functions are representable by a finite collection of a-vectors, let H be a set of a-vectors whose upper surface corresponds to V. The above three equations can be rewritten in terms of sets of a-vectors as follows: k a,z = {^+'1MatZa\ae^k-1} (2.16) '^ a = e < 2 (2.17) z€Z Hk = U K (2.18) aeA The symbol © means pairwise addition (i.e., N © ft' = {a + a'\a G ft A a' € ft'}). The key to incremental pruning is to reduce the set of a-vectors representing 20 max x s.t. b{a -a')>x Va' € N - {a} 6(s) > 0 Vs e S Table 2.1: LP-dominance test: vector a is dominated by H — {a} when x < 0. each value function in Equations 2.16, 2.17 and 2.18 by pruning all the dominated vectors (vectors that are not part of the upper surface). For example, in Figure 2.3, &2 and Q!4 correspond to conditional plans that are suboptimal and therefore can be removed without changing the upper surface. Dominated a-vectors can be detected in two ways: by pointwise dominance and by linear programming (LP). A vector a is pointwise dominated by a' when the expected total reward of a is less than or equal to a' for every state (i.e., a(s) < a'(s) Vs £ S). In Figure 2.3, 0:4 is pointwise dominated by 03. Note however, that 0:2 is not pointwise dominated by any single vector; it is dominated by a combination of vectors of the upper surface. This is detectable by an LP-dominance test (Table 2.1). The full DP procedure is given in Table 2.2. Its worst case running time requires the solution of 0(|.A||K f c - 1|l 2l) LPs. LPs are taken as a basic operation be-cause they are computationally intensive. This shows an exponential computational complexity with respect to the observation space. However, in practice, pruning helps to reduce considerably computation time. Moreover, for the class of polyno-mially action-output-bounded POMDPs [27]—which consists of P O M D P s such that for all actions a the size of (after pruning) grows polynomially with respect to —the reduction obtained by pruning makes the DP procedure tractable (i.e., polynomial in |^ 4.|, \Z\ and For finite horizon h, the incremental pruning algorithm determines an opti-mal policy irh by iterating the above DP procedure h times. A sequence N 1 , . . . , Kh) of sets of a-vectors is computed and the optimal policy is implicitly defined by the 21 P R O C E D U R E DPbackup{Kk-1) H f c <- 0 for each a G A do for each z € 2 d o K,z *~ prune({^ +jMajZa\cx G ~Rk~1}) <- prune (N* 0 N* J H f c « - prune(N f c U N£) return H f c E N D P R O C E D U R E Table 2.2: DP procedure last set ~Rh. In practice, the optimal policy can be represented explicitly as a map-ping from belief states to actions or as a finite state controller. If a mapping is used, then an action is stored with each a-vector of the h sets H l (1 < i < h). The action stored with a given vector ap is the first action a that would be executed when implementing the corresponding conditional plan /3 = (a, a). This scheme indirectly provides a mapping from belief states to actions since there is a mapping from belief states to maximizing a-vectors. At execution time, for time step i , the agent simply updates its belief state, determines the a-vector that maximizes its expected total return and executes the action stored with it. Alternatively, as pointed out by Kael-bling, Littman and Cassandra [22], the optimal policy can also be represented as a finite state controller. Explanations concerning finite state controllers are deferred to the next section when Hansen's policy iteration algorithm is introduced. For infinite-horizon POMDPs , an e-optimal policy (policy whose value func-tion differs from the optimal infinite-horizon policy 7r* by at most e for every belief state) is also found by iterating the DP procedure. The idea is to find a A;-step optimal policy 7rfc and to execute at every time step the action stored with the best a-vector in Hk. Let's call 7rfc and Vk the policy and value function corresponding to this strategy. nk differs from irk since at time step t the action prescribed by Trk is stored with the maximizing a-vector in H f c whereas for 7rfc it is stored with the 22 maximizing a-vector in N . A n important question concerning the quality of fc is: how far is Vk from the optimal infinite-horizon value function V*? If the Bellman residual, that is, the difference between Vk~l and Vk~2, is bounded by some 5 (i.e., sup6 \Vk~1(b) - Vk~2(b)\ < S) then one can show that Vk and V* differ by at most 2 < 5 7 / ( l — 7 ) for every belief state [32]. If 5 is picked to be e(l — /y)/2j, then sup \ Vk(b) — V*(b)\ < e and we say that nk is e-optimal. In practice, 5 can be made arbitrarily small since the Bellman residual decreases with each DP backup by a factor of at least 7 . 2.3.2 Policy Iteration A short description of Hansen's policy iteration algorithm is presented. It differs from value iteration algorithms because it conducts a search directly within the space of policies. On the other hand, the space of policies is huge, so it restricts its search to the set of policies that can be represented by finite state controllers. A finite state controller is essentially a directed graph with vertices labelled by actions and edges labelled by observations (Figure 2.4). Vertices do not (necessarily) correspond to world states or belief states, they correspond to conditional plans. The vertex corresponding to conditional plan /3 = (a, a) is labelled with action a and its outward edges correspond to the observation strategy a. At run time, the agent executes the action labelling the current active vertex. It then makes an observation z which is used to update the active vertex by following the outward edge labelled with z. This edge points to the next active vertex which corresponds to the conditional plan a(z). The initial active vertex is determined by selecting the maximizing conditional plan, that is, the conditional plan with a corresponding a vector that maximizes the expected total return for the initial belief state. The value function V* of a finite state controller 7r corresponds to the upper surface of the set of a-vectors ft7r associated with the vertices of IT. Hansen's algorithm can be used to solve discounted, infinite-horizon POMDPs . 23 Figure 2.4: Finite state controller for a simple POMDP with two actions and two observations. It computes a sequence of finite state controllers ( 7 T o , 7 r i , . . . ,nn) such that in the limit (when n —>• oo), 7r„ converges to the optimal policy ir*. That is, the value function of the controllers in the sequence increases monotonically and in the limit, converges to V*. Given a controller 7Tj, the next controller 7r,_|_i is obtained greedily in two steps: • Policy evaluation: compute the value function V"Ki of 7Tj. • Policy improvement: perform a dynamic programming backup and extract the next finite state automaton 7 T j + i . Policy evaluation essentially computes the set for some controller IT. This is done by solving a system of I^H^I equations of the following form: ap=(a,<r)(s) = -Ra(s) + 7 Pr(s'\s,a) Pr(z'\a>s')a<r(z')(s') s'es z'ez Each equation gives the expected total reward for executing the conditional plan /3 associated with some vector a £ ^ at some initial world state s € S. Policy improvement is the key step in Hansen's algorithm. It takes the set of a-vectors N71-* computed by policy evaluation and performs a DP backup as in incremental pruning. Let be the set of a-vectors resulting from the backup. The a-vectors in N!p are used to modify the vertices and the edges of the controller 7Tj 24 according to three simple rules, yielding the next controller 7 T j + i . We refer the reader to [13, 14] for the details of those rules as they are not essential to the development of this thesis. In practice, certain POMDPs have optimal policies corresponding to infinite state controllers. As with incremental pruning, one can find an e-optimal finite state controller by ensuring that the Bellman residual is small enough. The argument is identical to the one for incremental pruning since both use the same DP procedure to compute backups. Empirically, it has been observed that Hansen's algorithm requires fewer iterations than incremental pruning to converge to an e-optimal policy. On the other hand, each iteration of Hansen's algorithm carries a policy evaluation step and a DP backup, whereas an iteration of incremental pruning only performs a DP backup. In practice, because the running time of a policy evaluation step is negligeable when compared to a DP backup, Hansen's algorithm usually runs faster. Although it runs faster, its computational complexity is as intractable as incremental pruning since both iterate the same DP procedure. 2.4 Performance issues Solving P O M D P s is a notoriously hard problem. In fact, finding an optimal policy has been shown to be PSPACE-complete for finite-horizon problems [28] and verify-ing the existence of a policy with a value function greater than some threshold for a given initial belief state is undecidable [30]. Yet, P O M D P s remain a very attractive framework to conduct planning under uncertainty and numerous algorithms have been proposed in the literature. In practice, the P S P A C E completeness and undecid-ability of P O M D P s translate into two sources of intractability that afflict all current algorithms. In this section, a brief review of those sources of intractability and how some researchers have tried to mitigate them using factored representations is pre-sented. Finally, as mentioned earlier, although the complexity of solving P O M D P s is not the focus of this thesis, it will influence the design of some algorithms in 25 Chapters 3 and 4 and the experiments in Chapter 5. 2.4.1 S o u r c e s o f I n t r a c t a b i l i t y All current algorithms that solve POMDPs exactly are plagued by two sources of intractability: • The number of a-vectors may grow exponentially with the size of the obser-vation space Z and doubly exponentially with the horizon h. • The dimensionality of each a-vector is equal to the size of the state space S. The first problem is easily observed when examining the DP procedure used in incremental pruning and in Hansen's algorithm. For each backup, 0(|>l||K|l'Zl) a-vectors may be generated if no vector is pruned. Consequently, at the kth iteration, there could be as many as 0(LA|*|Npl ) a-vectors. As for dimensionality, most real world problems tend to have large state spaces. In many domains, the state space is defined by a set of variables such that each state corresponds to a joint instantiation of those variables. Hence, the number of states (and the dimensionality of a-vectors) is exponential in the number of state variables. 2 . 4 . 2 F a c t o r e d R e p r e s e n t a t i o n Recently, some attention has been devoted to approaches that exploit some type of problem structure to essentially reduce the size of the state space. In particular, the use of factored representations that resemble classical A l representations allow the manipulation of a compact encoding of the state space. This encoding lets us reason at the variable level instead of the explicit state level, leading (potentially) to an exponential reduction in complexity. Decision trees (DTs) [2] and algebraic decision diagrams (ADDs) [18, 15] are examples of such encodings that can exploit 26 a-vector D T ADD a ( X Y Z ) a ( X Y ~ Z ) a ( X ~ Y Z ) a ( X ~ Y ~ Z ) a (~XYZ) a (~XY~Z) a ( ~ X ~ Y Z ) 2 2 2 2 2 4 3 3 2 3 3 Legend: false true a (~X~Y~Z) 2 4 2 4 Figure 2.5: D T and A D D example problem structure and have been shown to significantly speed up solution algorithms for several MDPs [18] and POMDPs [15]. DTs and ADDs can improve the running time of incremental pruning and Hansen's policy iteration by allowing the manipulation of an abstract state space instead of the explicit state space S [15]. More precisely, linear functions of the state space (such as a-vectors, belief states, transition functions and observation functions) can be compactly represented by aggregating some world states with identical values into a single abstract state. Figure 2.5 shows tne D T and A D D representations of an a-vector. For DTs, an abstract state corresponds to a partial assignment of the state variables that define the state space. Each branch (path from the root to a leaf) encodes such a partial assignment by instantiating all the variables it traverses. The leaf at the end of a branch is labelled with the value that is shared by all the world states that satisfy the corresponding partial assignment. A n A D D is roughly speaking a D T where branches are allowed to share identical subtrees. Consequently, ADDs can generate much coarser partitions of the state space than DTs and therefore, they will be used throughout the rest of this thesis. Factored representations can speed up several operations on a-vectors such as addition, pointwise multiplication, dot product, pointwise dominance, LP-dominance, etc. Al l these operations have a running time that depends on the dimensionality 27 of the vectors involved. When using ADDs, the dimensionality is reduced to the size of the intersection of the partitions used to represent the vectors involved. The intersection of two partitions p\ and P2 is a partition p such that all the abstract states in p are the intersection of an abstract state in p\ and an abstract state in P2-2 For instance, when adding two vectors, ot\ and 0:2, only values of abstract states that aggregate the same world states can be added together. These common abstract states happen to be the intersection of the abstract states used to represent a\ and 0.2-Most exact algorithms for POMDPs (including incremental pruning and Hansen's policy iteration) make use of a DP procedure similar to the one described in Section 2.3.1. The running time of this procedure can be significantly improved by the use of a factored representation [15]. More precisely, the speed up comes from an improvement in the running time to solve LPs, which are the most compu-tationally intensive operations in the procedure. ADDs can speed up LP-dominance tests to the extent where the intersection of the partitions of the a-vectors involved is smaller than the full state space. This fact is important for two reasons: • The experiments carried out in Chapter 5 will be biased towards P O M D P s that exhibit enough structure to allow a-vectors with partitions that "intersect well". • The algorithms for computing error bounds in Chapters 3 and 4 are very similar to incremental pruning and make extensive use of linear programs that resemble LP-dominance tests. Therefore, the design of those algorithms will be influenced in a way to take advantage as much as possible of the speed up enabled by ADDs. 2 Hansen and Feng describe an algorithm to compute the intersection of some partitions in [15]. 28 2.5 Belief State Monitoring The previous sections were concerned with the offline problem of solving a P O M D P . In this section, an overview of the online belief state monitoring problem is pre-sented. Depending on the representation of a policy (as a mapping from belief states to actions or as a finite state controller), the agent may or may not be re-quired to monitor its belief state. Hence, our first concern will be to determine when and why belief state monitoring is desirable. Following, a brief overview of some exact and approximate methods for belief inference is presented. Dynamic Bayesian networks (DBNs) are introduced as a popular exact method. Despite its use of fac-tored representations, the method is intractable for most non-trivial POMDPs , so we turn to approximate methods, among which projection schemes and density trees are reviewed. 2.5.1 Motivation When a policy is represented as a mapping from belief states to actions, belief state monitoring is required; in contrast if it is represented by a finite state controller, it can be executed directly. In general, the optimal policy of any finite horizon P O M D P can be represented by a finite state controller as pointed out by Kaelbling, Littman and Cassandra [22]. As for infinite-horizon POMDPs , Hansen's policy iteration algorithm can be used to find an e-optimal policy, also represented as a finite state controller. At a first glance, the reader may wonder about the need for belief state monitoring, however three reasons may justify it in practice: e-optimal finite state controllers may not be appropriate representations for infinite-horizon policies In many situations, the pratitioner may model an infinite-horizon, undiscounted P O M D P as an infinite-horizon, discounted P O M D P . This could be for computa-tional purposes or simply to give a sense of urgency to the planning agent. In either 29 case, the practitionner expects the agent to execute the policy for an infinite number of steps and it also expects the quality of the policy to remain constant over time. In other words, the expected total future reward for a given belief state should be the same regardless of the number of steps executed so far. If the policy is stationary, its quality is constant; however that is not the case for nonstationary policies. It turns out that mappings from belief states to actions represent stationary policies whereas finite state controllers don't [16]. At this point, it is not known to what extent the quality of a controller's policy deteriorates over time. In theory, an e-optimal controller is guaranteed to yield an expected total discounted reward within e of the optimal policy only for the initial time step. As time goes, the discount factor scales down the rewards as well as any divergence between the optimal policy and the controller's policy. Currently, the only way to prevent a deterioration in quality is to periodically reset the active vertex of the finite state controller to the best vertex given the current belief state. Knowledge of the current belief state requires that one perform belief state monitoring. Most approximation algorithms for solving POMDPs represent policies as mappings from belief states to actions As explained in the previous section, all current exact algorithms are intractable. Therefore, several heuristic approaches have been suggested to solve P O M D P s ap-proximately [17]. However, most of them assume a mapping from belief states to actions which requires belief state monitoring. Thus, the techniques described in the coming chapters are likely to integrate well with existing belief-based methods to solve P O M D P s approximately. 30 Belief state monitoring may be desirable in its on right for explanatory purposes Knowledge of the current belief state provides useful information to the practitioner for understanding the subtleties of the policy in execution. This information can also be used to validate the reward, transition and observation functions which are usually based on rough estimates determined by an expert. 2.5.2 Dynamic Bayesian Networks (DBNs) The task of belief state monitoring consists of updating the current belief state according to the previous action and observation. More precisely, bt+\ is obtained from bt, at and zt+i as in Equation 2.4. When represented as a vector, a belief state has dimensionality equal to the size of the state space. In general, a belief update requires some computation that is a low order polynomial in the size of the state space. When the state space is large (i.e., exponential in the number of state variables) the task becomes intractable. Once again, factored representations have been proposed to mitigate the curse of dimensionality. Dynamic Bayesian networks (DBNs) [7] are very popular models that (potentially) allow efficient belief inference. The key is to exploit con-ditional independence to reason at the variable level instead of the state level. A D B N is an acyclic graph that encodes the transition and observation functions at each time step. Figure 2.6 illustrates a two-slice D B N for a simple P O M D P of three state variables (W, X and Y) and one observation variable (Z). The unprimed state variables form a slice for time step t and the primed state variables form another slice for the next time step, t + 1. The edges in the graph summarize conditional independence between variables. That is, a variable is conditionally independent from all its ancestors given its parents. The transition and observation functions are numerically represented by conditional probability tables (CPTs), which indicate the conditional distributions Pr(v\pl,pl,... ,p") of each variable v given its parents 31 t t+1 W Y Pr(W'|W,Y) ® ® © 0 0 0 1 1 0 1 1 0.8 0.4 0.3 0.5 © Figure 2.6: Two-slice D B N pl,Py, • • • ,Py. As an example, the C P T for Pr(W'\W,Y) is given in Figure 2.6. Conditional independence can be leveraged to compute the next belief state bt+i from the current belief state bt (given some action a and some observation z). In the D B N , bt and bt+i correspond respectively to the joint distributions Pr(W, X, Y) and Pr(W, X', Y'). A belief state update using the D B N paradigm essentially asks the question: Pr(W',X',Y'\Z = z)l The answer can be found using a variety of algorithms. A common method is to build a secondary structure, called a clique tree, and to perform belief inference on this structure. A clique tree is a compact factored representation of the joint distribution Pr(W, X, Y, W', X', Y', Z) that ex-ploits variable independence. The reader is referred to Huang and Darwiche [19] for a high level overview of clique tree construction. What is important to know is that clique tree encodings are exponential in the size of the largest clique and roughly speaking, clique size increases with dependencies (correlations). Assuming monitoring is done using the clique tree representation of a D B N , a belief update is performed in three steps (see [19, 25] for more details on inference with DBNs using clique trees): • Construct a clique tree that encodes the variable dependencies of the system dynamics (for a specific action and observation). 32 • Initialize the clique tree with the transition probabilities, the observation prob-abilities and the joint distribution of the state variables at the current time step (current belief state). • Query the tree to obtain a joint distribution of the state variables at the next time step (next belief state). The amount of computation required for those three steps is also exponential in the size of the largest clique. This suggests that monitoring can be efficient when the variables in each slice (defining each belief state) remain fairly independent as time goes. Unfortunately this rarely occurs in practice. As observed by Boyen and Koller [3], although the variables in the initial belief state may be independent and although at each time step only a small number of state variables become correlated, over time these correlations "bleed through" the D B N , rendering most (if not all) state variables dependent after some time. Figure 2.7 shows several slices of an "unrolled" D B N (observations are omit-ted for simplicity). Suppose that the variables defining the current belief state at time step i are all independent. At the next time step, i + variables sharing at least one parent become correlated and a few pairs of correlated variables show up. At subsequent time steps, the subsets of correlated variables (variables that share at least one ancestor) keep on growing until, at time step t + 3, the state variables are fully correlated. This is typical of most real world problems. Thus, exact belief state monitoring using DBNs usually remains prohibitively expensive. 2.5.3 Approximation Methods In the literature, several methods have been proposed to efficiently approximate the belief state monitoring task. Among them, projection schemes and density trees are reviewed since the former integrates well with DBNs whereas the latter is closely related to DTs and ADDs. 33 I i subset of correlated variables Figure 2.7: Unrolled D B N with no observation Projection schemes Boyen and Roller [3] devised a clever method to ensure that state variables remain fairly independent during the execution of a policy. Intuitively they consider pro-jection schemes whereby the joint distribution of a belief state is approximated by the marginal distributions of some subsets of variables. They assume that these subsets partition the variable set in disjoint subsets. For each subset, its marginal is computed and the approximate belief state is formed by taking the product of the marginals as if they were independent. Thus only variables within the same subset can remain correlated in the approximate belief state. In this thesis, a projection scheme is formally defined as a set of subsets of variables such that all variables are in at least one subset. This allows marginals with overlapping subsets of variables. For instance, the projection S = {XY, YZ} approximates the joint Pr(X,Y, Z) with the marginals Pr(X,Y) and Pr(Y,Z). Those marginals are stored in lieu of the belief state since they define implicitly the approximate belief state. A n explicit joint of the approximate belief state can be computed by constructing a clique tree with cliques that correspond to the subsets 34 of variables over which those marginals are defined. This clique tree, which encodes a belief state, is different from the D B N clique tree of Section 2.5.2 used for Bayesian inference. Note that some projection schemes with overlapping subsets are not useful because they don't correspond to any clique tree, therefore they will be discarded in practice. Given a projection scheme S (with a corresponding clique tree), one can perform an approximate belief state update as follows: • Construct a D B N clique tree that encodes the variable dependencies of the sys-tem dynamics (for a specific action and observation) and the correlations that have been preserved by the marginals representing the current approximate belief state b%. • Initialize the D B N clique tree with the transition probabilities, the observation probabilities and the marginals representing the (approximate, factored) joint distribution of bt-• Query the D B N clique tree to obtain the joint distribution bf over the variables at the next time step. • Project bf according to scheme S by computing the marginals representing the approximate belief state bt+i = S(bf). The complexity of belief state monitoring, which is exponential in the size of the largest (DBN) clique, is effectively reduced by choosing an adequate projection scheme that prevents (DBN) cliques from growing beyond some threshold. It is also important to note that projection schemes perform nonlinear ap-proximations of a belief state. In other words, the probabilities of each world state in the approximate belief state are nonlinear combinations of the probabilities of the world states in the exact belief state. For instance, the projection S = {X, Y} maps the exact belief state b to the approximate belief state S(b) = b according to 35 the following nonlinear equations: b(xy) b(x)b(y) [b(xy) + b(xy))(b{xy) + b(xy)) b(xy) b(x)b(y) [b(xy) + b(xy))(b{xy) + b(xy)) b(xy) b(x)b(y) {b(xy) + b(xy))(b{xy) + b(xy)) b(xy) b{x)b{y) (b(xy) + b(xy)){b(xy) + b(xy)) The nonlinear properties of projection schemes will have an adverse effect on the quality of the error bounds computed in the next chapter. Density Trees Although, the value-directed framework introduced in this thesis is exemplified with projection schemes (mainly due to their nice integration with DBNs), it also applies to any linear approximation method. In fact, it is better suited for linear methods because the error bounds introduced in the next chapter can be made tighter. In this section, we briefly describe density trees [26] as they are a very good example of a linear approximation method and because they are closely related to DTs. The de-scription given below is syntactically different from that of Roller and Fratkina [26], but it is conceptually equivalent. A density tree defines an abstract state space representable by a D T that belief states are forced to fit in. The idea is to assume that all the world states aggregated in a belief state have the same value. Thus, a belief state is "compressed" in a D T by assigning to each abstract state the average probability of all the world states it aggregates. Figure 2.8, shows how some belief state b is approximated to S(b) when applying some density tree S. A density tree with an abtract state space polynomially-sized in the number of variables offers an exponential reduction in the number of dimensions. It should also be clear to the reader that density tree approximations are linear since averaging is a linear operation. Finally, an approximate belief update using density tree S is performed as follows: 36 X X S(b) X 0.05 Y 0.05 Y Z 0.15 0.25 0.15 0.10 0.40 Figure 2.8: Density tree approximation • Let bt and Ma>z be in factored forms such as DTs or ADDs. • Compute bf = btMa>z/K by manipulating the factored representations. • Compute the approximate belief state bt+i = S(bf) by aggregating (through averaging) the leaves of bf until it satisfies the abstract state space defined by the density tree S. 2.6 Thesis Assumptions This section ends the background material on P O M D P s and belief inference by stating the assumptions underlying the value-directed framework introduced in the following chapters. The framework assumes that: • A P O M D P has been solved and an optimal (or e-optimal) policy is already computed. • The policy is given by a mapping from belief states to actions. 37 The value function corresponds to (or is approximated by) the upper surface of a finite set of a-vectors. Since the P O M D P has been solved, this set of a-vectors is assumed to be tractable. This means that the number of a-vectors as well as their effective dimensionality is reasonable. Here, by effective dimensionality we mean the reduced dimensionality obtained by a factored representation such as ADDs. Exact belief state monitoring is intractable and therefore needs to be approx-imated. The goodness of an approximation method is measured by the loss in expected total reward. We perform an offline search to find a good approximation method that en-ables fast online belief state monitoring. 38 Chapter 3 Value-Directed Approximations We now introduce a general theoretical framework to analyze approximation meth-ods from a value-directed point of view. The goal of this analysis is threefold: • To provide some insights regarding the impact of approximations on decision quality. • To develop bounds for the loss in expected value due to the use of a given approximation method. • To develop algorithms that search within a class of methods for an approxima-tion scheme that sacrifices as little as possible decision quality (by minimizing the bounds on expected loss). The chapter is organized as follows. Sections 3.1 and 3.2 assume that we have been given some approximation scheme S for performing efficient belief up-dates, as well as the value function of an optimal policy that we wish to execute. The goal is to derive error bounds for applying the approximation scheme S while executing the optimal policy. Section 3.1 starts by analyzing the simple case where a single approximation is performed at some time step and Section 3.2 generalizes this analysis to the situation where the belief state is approximated repeatedly (i.e., at every time step). 39 It is important to note that this analysis is general in the sense that it can accomodate a wide range of approximation methods. In this thesis, the framework is illustrated by the class of projection schemes; however all the observations made and the bounds derived also apply to any linear approximation method (including density trees). Projection schemes were picked mainly due to their tight coupling with DBNs which are very popular for exact inference in dynamical systems. Section 3.3 makes use of the bounds derived to develop algorithms that search for a good projection within the class of projection schemes. The class is first organized in a lattice which highlights the nicely structured partial ordering induced by the error bounds. Then we suggest a simple greedy algorithm that uses the lattice to guide its search. The reader should also be warned that the framework introduced in this chapter is mainly theoretical. That is, the analysis performed is conceptually correct, but the proposed bounds are loose and the suggested algorithms are designed to be analyzed easily, not to be efficient. Chapter 4 addresses these practical issues. 3.1 Plan switching Implementing a policy represented as a mapping from belief states to actions requires that one maintains a belief state, plugging this into the value function at each step, and executing the action associated with the maximizing a-vector. When the belief state b is approximated using an approximation scheme S, a suboptimal policy may be implemented since the maximizing vector for the approximate belief state S(b) will be chosen rather than the maximizing vector for the exact belief state b. Furthermore this mistaken choice of vectors (hence actions) can be compounded with each further approximation at later stages of the process. To bound such error, we first define the notion of plan switching. We phrase our definitions in terms of finite-horizon value functions, introducing the minor variations needed for infinite-horizon problems later. 40 • S(b) b b Figure 3.1: Relevant belief states at stage k Suppose with A; stages-to-go, the true belief state, had it been monitored accurately to that point, is b. However, due to previous belief state approximations we take our current belief state to be b. Now imagine our approximation scheme has been applied at time k to obtain S(b). Given ftfc, representing Vk, suppose the maximizing vectors associated with b, b and S(b) are ai, a,<i and 0:3, respectively (see Figure 3.1). The approximation at stage k mistakenly induces the choice of the action associated with 0:3 instead of 0:2 at 6; this incurs an error in decision quality of b • — b • 0:3. While the optimal choice is in fact OL\ , the unaccounted error b • a\ — b • 0-2 induced by the prior approximations will be viewed as caused by the earlier approximations; the goal at this point is simply to consider the error induced by the current approximation. 3.1.1 Switch set computations The purpose of this section is to identify when the course of action is modified by an approximation scheme S. Assuming the current belief state is b, the future course of action is given by the conditional plan corresponding to the maximizing a-vector for 41 1 1 1 ^ a 3 ^ a 2 ^cij Figure 3.2: Regions for each maximizing a-vector b. As long as S approximates b to some belief state S(b) with the same maximizing a-vector, there is no loss in expected return since the same conditional plan gets executed. In fact, the maximizing vector a for belief state b defines a region Ra of belief space in which S(b) can lie without altering the future course of action. In general, the set of a-vectors that make up the upper surface of a value function partition the belief space in regions Rai such that all belief states in a region are mapped to the same maximizing a-vector.1 Figure 3.2 shows the regions R a i , Ra^ and Ra3 defined by the vectors a\, 0,2 and 03. The idea of this section is to pick some region Ra and to identify all the other regions Ra> such that there exists a belief state b £ Ra that gets mapped to S(b) € Rai. More precisely, we identify for each a G N ' , the set of vectors Suig(a) that the agent can switch to by approximating (with S) its current belief state b given that b identifies a as optimal. Formally, we define 1 Belief states on the boundaries of adjacent regions have more than one maximizing a-vector, however this doesn't bear any consequence. If a unique maximizing a-vector is required, ties can be broken by always choosing the maximizing vector that comes first in some predetermined ordering of the vectors. 42 Figure 3.3: The Switch Set Su^fa) of a 3 Swks{a) = {a' € K f c : 36Vo(6 • a > b • a, S{b) • a' > 5(6) • a)} Intuitively, this is the set of vectors we could choose as maximizing (thus implementing the corresponding conditional plan) due to belief state approximation. In Figure 3.3, we see that 5105(0:3) = {0:1,0:2,0:4}. The set Swks(ai) can be identified readily by solving a series of 0(|N f c|) op-timization problems. Each optimization problem tests the possibility of switching to a specific vector aj 6 K f c and it is formulated as a (possibly nonlinear) program (Table 3.1). It is interesting to note the similarity between switch test programs (Table 3.1) and dominance test LPs (Table 2.1). In fact, if we remove constraints of type 5(6) • (aj — a{) > d, they are identical. The objective function of a switch test program has a positive value whenever there is a belief state b such that a$ is optimal at 6, and aj is optimal at 5(6). In fact, we need only find a positive feasible solution, not an optimal one, to identify aj as an element of Swg(ai). For linear approximation schemes (such as density trees), these problems 43 max x s.t. b • (ai — ai) > x VI ^ i 5(6) • (ptj -at)>x VI + j b(s) > 0 Vs Table 3.1: Switch test program to determine if there exists a belief state b such that the projection 5 leads to a switch from a, to aj. The variables are x and each component b(s) of the vector b representing a belief state, ai, aj, a\ and 5 are fixed and therefore yield the variable coefficients. are easily solvable linear programs (LPs). Unfortunately, projection schemes are nonlinear, making optimization (or identification of feasible solutions) more difficult. On the other hand, a projection scheme determines a set of linear constraints on the approximate belief state 5(6). In general, for POMDPs with binary variables, there is one linear constraint for each subset of the marginals defined by the projection scheme.2 For instance, consider the projection scheme 5 = {CD, DE} for a P O M D P with 3 binary variables. This projection imposes the following linear constraints on 5(6): 6(0) = 6'(0) 6(C) = b'{C) b{D) = b'{D) b(E) = b'(E) b(CD) = b'(CD) b(DE) = b'(DE) Here 6' denotes 5(6) and b(XY) denotes the cumulative probability (accord-ing to belief state 6) of all states that assign the value true to variables X and Y (i.e., b(CD) = b(cde) + b(cde)). 6(0) is the cumulative probability of all states (which is always 1). These constraints define an L P that can be used to construct a superset Sws(ai) of Swg(ai) (see Theorem 1). Given scheme 5 = { M i , . . . , Mn}, we define the L P in Table 3.2. When a feasible positive solution exists, aj is added to the set Sws(ai), though in fact, it may not be a member of Swks(ai). If no positive fc solution exists, we know aj is not in Sws(ai) and it is not added to Sws(ai). 2For POMDPs with non-binary variables, there is more than one equation per subset. 44 max x s.t. b • (oii — ai) > x VI ^ i b' • (aj -afi>x Ml + j b'(M) = b(M) V M C Mi, l < l < n ZsKs) = l b(s) > 0 Vs b'(s) > 0 Vs Table 3.2: LP-switch test for projection schemes. The variables are x and each component b(s) and b'(s) of the vectors b and b' representing belief states, CCJ, aj, ai and M , are fixed and therefore yield the variable coefficients. T h e o r e m 1 Let Sws(a) and Sws(a) be the switch sets respectively constructed us-ing the switch tests of Tables 3.1 and 3.2. Then, Sws(a) C Sws{a). P r o o f Since a vector a' is added to Sws(a) and Sws(a) when the switch tests of Tables 3.1 and 3.2 have a positive feasible solution, it suffices to show that whenever the switch test of Table 3.1 has a positive feasible solution, then the switch test of Table 3.2 also has a positive feasible solution. Given a belief state b for which Table 3.1 has a positive objective function, then in Table 3.2, if we keep b the same and set b' to S(b), the objective function is also positive. • While the number of constraints of the type b(M) = b'(M) is exponential in the size of the largest marginal, we expect that the number of variables in each marginal for a useful projection scheme will be bounded by a small constant. In this way, the number of constraints can be viewed as constant (i.e., independent of state space size). The LP-switch tests in Table 3.1 (linear approximations) and Table 3.2 (pro-jection schemes) are computationally intensive. Their complexity is similar to that of LP-dominance tests since they all have 0(|<S|) variables and 0(|N f c|) constraints. Although the number of L P variables is exponential in the number of state variables, factored representations such as ADDs can be used to aggregate L P variables (which 45 really correspond to world states). As with L P dominance tests, each constraint in LP-switch tests can be encoded with an A D D that potentially reduces the effective state space. The actual speed up induced by ADDs will be determined by the size of the intersection of the abstract state spaces defined by the A D D representation of each constraint. In practice, density trees often have small intersections, whereas projection schemes don't. In fact one can show that for projection schemes, the resulting abstract space is always the whole state space. This is because of the constraints of type b(M) = b'(M), Each such constraint where M is a single variable has an A D D representation defining a very small partition of two abstract states: the states for which variable M is true versus the states for which variable M is false. By definition, the state space is the intersection of those partitions, so if for each variable X there is a constraint b(X) = b'(X), then the intersection is the whole state space. It turns out that for all projection schemes, each variable has a corresponding constraint b(M) — b'(M) where M is that variable. This is because all variables must be contained in at least one marginal of the projection scheme. Hence, LP-switch tests for projection schemes do not benefit from ADDs. On the other hand, it may be possible to still get a speed up by extending the A D D concept in such a way that we would aggregate, not only states with identical values, but also states whose values are linear combinations of each others. This refinement is a research problem in its own that remains to be explored. In contrast, LP-switch tests for density trees do not suffer from this problem since density trees yield linear approximations. Linearity allows us to use the L P -switch test of Table 3.1 which doesn't have any constraints of the type b(M) = b'(M). In summary, the switch set of an a-vector identifies all other a-vectors (there-fore conditional plans) that may be executed as a result of a single approximation S at the current time step. At stage k, the value function is determined by a-vectors, so there are 1^ *1 switch sets and each of them requires the solution of 46 LPs, for a total of 0(|tt f c| 2) LPs. Once again, LPs are taken as a basic operation since they are computationally intensive. In comparison, when computing the DP procedure may require as few as f2(|Kfc|) LPs if no vector gets pruned. However, in practice, several a-vectors are usually pruned during the construction of K f c , hence the running time to construct all switch sets tends to be similar to that of the DP procedure. 3.1.2 Switch set error bounds Switch sets give us a very useful tool to bound the loss in expected value attributed to a single approximation. The idea is simply to measure the difference in expected return between the optimal conditional plan (had we not approximated the current belief state) and the worst conditional plan we could switch to. Let B3s(a) be an upper bound for the loss at stage j when approximation S is used and when a is viewed as optimal: BJs(a) = max max b • (a — a') (3-1) b a' e Sin's (a) Also, let Bs be the greatest error introduced for any a-vector: \ BJS = max B3s(a) (3.2) In Equation 3.1, although the exact switch set Swg is used, one can also define Bs in terms of a superset Sivs with the consequence of a looser bound. In practice, since error at a belief state b is simply the expectation of the error at its component states, Bs(a) can be determined by comparing the vectors in Siifg(a) with a componentwise (with the maximum component difference being BJs(a)). For a &-stage, finite-horizon P O M D P , we can now bound the error in decision quality due to successive approximations with S. One simply has to figure out the bounds BJS for j stages to go. The cumulative bound Ug (for k stages) is the discounted sum of each stage's bound: k Uks = Y l k - 3 & s (3.3) 3=1 47 As for infinite-horizon POMDPs , two possibilities arise: either we are given the set K* corresponding to the optimal value function V* or we only have access to the set H f c which implicitly determines the e-optimal value function Vk. For the optimal case, the bound Ug is pretty straightforward. It suffices to compute the switch sets of the vectors in the optimal set and to derive the one-step error bound Bg. The upper bound Us on the loss incurred by applying S indefinitely is simply the infinite discounted sum of Bs: As for e-optimal policies, we can derive a bound Ug, but this requires some work. We normally get an e-optimal policy Ttk by using at every step the same mapping from belief states to actions provided by the set Hk representing the optimal fc-step value function Vk. If we had access to the set ftfe representing Vk, we could compute the switch sets of each vector in H f c and derive a one step bound Bg. The cumulative bound Ug would simply be the infinite discounted sum of Bg: 61 = * L (3.5) < (3.6) 1 - 7 In general, Vk is not piecewise-linear nor convex so H f c is not (necessarily) a finite set of vectors whose upper surface corresponds to Vk. ftfc is a possibly infinite set of vectors such that each of them corresponds to the conditional plan that is prescribed by frk for some belief state b. Unfortunately, we don't know ftfc and computing it is an impractical task as it is a possibly infinite set. On the other hand, we know that Vk and Vk are fairly close (within e/2 of each other), so one would expect Bs and Bs to be fairly close. In fact they are, but not as close as Vk and Vk are. We will show below that the difference between Bg and Bg can be bounded by some small number [x. Unfortunately there is no relationship between y. and e other than [i > e. Assuming Bg < Bg + fi, which we will prove shortly, then Equation 3.6 follows. 48 In order to show that Bs < Bs + fi, we need to establish 3 lemmas and to introduce some more notation. Define the LQO distance between two sets of a-vectors N71" and Hn' as follows: IIN"" - N^'lloo = max \\ab - a'Joo (3.7) 6GA(5) Here, ab and a'b are respectively the a-vectors in and K71"' that correspond to the conditional plans prescribed by n and TT' at belief state b. When the value functions Vv and V~7r' are piecewise-linear and convex, ab and a'b are essentially the maximizing vectors for belief state b. Note however that, in general, this is not the case for value functions (such as Vk) that lack these properties. The distance measure in Equation 3.7 is essentially a generalization of the LQO distance between value functions to an Loo distance between sets of a-vectors. This new distance measure gives us a handle to compare Bs and Bs. Roughly speaking, those bounds are defined in terms of a-vectors, so when ttk and Hk are close (their LQO distance is small), then we are able to show that Bg and Bg are also close. Below, Lemma 1 relates the LQO distance between and ttk to the distance between Bs and Bk. Lemma 1 If \\Hk - Nfe||oo < fi/2 then Bks < Bks + fi. Proof Let's introduce an alternative definition for Bs(a) that is more convenient for this proof. The expression Bg(a) was initially defined in Equation 3.1 as an upper bound on the loss in expected total return due to the use of approximation S at step k assuming that the maximizing vector is a. The assumption that a is optimal implies that the current belief state b lies in the belief space region Ra. Using this region notion, one can redefine Bs(a) with the following conceptually equivalent expression: Bq(a) — max max b • (ar — aQ,r\) 49 The above expression can also be adapted to define Bs(a), but with one slight semantic difference. Bs(a) = max max b • {&-b - &s(i)) Since the value function Vk is not (necessarily) piecewise-linear nor convex, the region R& is not (necessarily) the belief space region for which a dominates in It is rather the region for which the policy jrk prescribes the conditional plan corresponding to a. Similarly, the vectors a~b and a s ^ correspond to the conditional plans prescribed by 7Xk at belief states b and S(b). We are now ready to prove the lemma: Bq = max max max b • (ar — ac/i\) s beA(s) b e R & v b SW = m ^ - m a X b ' (&~b ~ a ^ + b ' (ab ~ aS(b)) + b • (aS(b) ~ &S(b)) < max max max ^ + b • (ab - as(l)) + £ (3.8) - S 6 ™ S b' {a'b ~ a sCb) ) + M ( 3 , 9 ) = Bks + p In Equation 3.8, b • (a~b — ab) < \\a~b — a j | | o o < A*/2 and b • {<xsfy — as(i)) — 11^6 — a f c l l o o < A*/2. In Equation 3.9, the regions R& are replaced by the regions Ra since every region R& is a subset of some region Ra. • The above lemma provides a step in the right direction for the computation of Bk, however it assumes the knowledge of \\kk — H f e | | o o - As mentioned earlier, we don't have access to Hk and therefore we don't know its distance from On the other hand, in the DP procedure, the value function Vk is not available either and yet, its distance from Vk can be evaluated. This is made possible by observing that Hd backups contract the distance between value functions by a factor of at least 7. Assuming d is a mapping from belief states to actions, an Hd backup is similar to a DP backup except that the action executed at the first time step is not necessarily 50 the one maximizing the expected total reward, but rather the one prescribed by the mapping d. Formally, we define HdV as follows: (HdV)(b) = R(d(b),a) + 7 E P ( b d z i b ) l6> d ( b ) ) V ( b i i b ) ) z Below, Lemma 2 essentially shows that a generalized version of Hd, call it ' H d , is also a contraction mapping for the distance between sets of a-vectors. Semantically, T-Ld and H d are the same, however T-Ld operates on sets of a-vectors whereas Hd operates on value functions. %dft = {ab\ab = Rd(yb) +-y^2Md(b^zabd{b) for some a^m G ft} z Lemma 2 Let ft and ft' be sets of a vectors, then T-Ld is a contraction mapping: ||Hdft - Hdft'||oo <7l|K-ft' | |oo. Proof Let abHdn and a ^ N ' be the a-vectors respectively prescribed by %dft and H^W at belief state b. Let a be the action prescribed by d at belief state b. We need to show that for any belief state b, | | a ^ d H — a^^'Hoo < 1^ when ||« — «'Hoo = | | a ^ N - a ^ ' H o o = ||i? a + 7 ^ M a , z a \ - R a + jY,M°>*a%W°° z z = 7 l | M a ^ M 2 ( a ^ - a 6 H : ) | | 0 0 2 < 7iiEM^4-4)ii°° ( 3 - 1 0 ) z < 7^ (3-11) In Equation 3.10, MA is a transition matrix such that the components of each row sum up to 1. Matrices with this property can only reduce the Loo distance. In Equation 3.11, the sum of all the matrices MZ is the identity matrix. Since l l a 6f ~~ a%W°o i s a t m o s t V>> t n e n II !LZ Mz(a\\ - a^a)||oo is also bounded by ip. • 51 The above lemma shows that any T-L backup constitutes a contraction map-ping. If we let dk be the mapping from belief states to actions encoded by the set ttk, then it should be clear that K f c = W ^ N * - 1 and similarly, N* = (Hdh)°°'Hk~1. Below, Lemma 3 shows how the contracting property of Hdk and the fact that 9t,k and ftfe are obtained by /Hd,k backups allow us to bound the distance between ftfc and ftfc. The technique used is the same as for bounding \\Vk — I^ f c | | co given the Bellman residual, however, working with sets of a-vectors instead of value functions. Lemma 3 If \\Hk - N * - 1 ^ = il>, then ||K f c - N*||oo < 7^/(1 - 7). Proof l l ^ - ^ I U = < < • The above lemma provides the last piece of information necessary to relate Bk and Bk. To summarize, we can estimate the bounds Uk and Bk as follows: Theorem 2 Given the sets ftfc and ftfc_1 such that ip = ||ftfc - Nfc-1||oo> let /J, = 27^/(1 — 7), then 1. Bk <Bk + n 2. tlk < (Bk + u)/(l - 7 ) Proof Compute ip = — ^k~1\\0o- By Lemmas 2 and 3, we know that 11^ - ^Hoo < -7-0/(1 - T) = M/2 \\{Hd")00Xk-1 -HdkHk-1\\00 d \lv>fc—1 I 1=1 00 £ 7 * | | N * _ N f c - i | i=l 7^ / (1 -7 ) 52 It follows that by Lemma 1, Bk < Bk + fi and consequently, using Equation 3.5: Uk < (Bk + n)/{l-j) • It is interesting to compare the value ip to 5 (Bellman residual) as well as the value \JL to e. Since the LQO distance between sets of a-vectors is at least as great as the Loo distance between the value functions they represent, it follows that tp > S. Similarly, since ii and e share the same relationship with respect to ip and S, it follows that \i > e. There is one important distinction that must be made between LJ, and e. Since the DP backup is a contraction mapping for the Loo distance between value functions, one can make the Bellman residual, and consequently e, arbitrarily small by doing enough DP backups. Although Lemma 2 shows that any Tid backup is a contraction mapping with respect to the Loo distance between sets of a-vectors, the author has been unable to prove or disprove the same for DP backups. This is an important question that remains to be solved. In the event where DP backups are not contraction mappings for the Loo distance between sets of a-vectors, then the practitionner has no control on ip and [x and therefore it may not be possible to reduce them past an acceptable threshold. This means that the estimates of Uk and Bk could be much worse than their actual values. 3.2 Alternative plans The cumulative error induced by repeated approximations can be bounded in a tighter way than simply taking the discounted sum of the B bounds (as it is done 53 to compute the U bounds). The idea is to generate the set of alternative plans that may be executed as a result of both current and future approximations. Suppose that an agent, due to approximation at k stages to go, changes its belief state from 6 to 5(6). This can induce a change in the choice of optimal a-vector in ttk, say from ap1 to ap2 where Pi = (a\,ai) and fa = (02,02)- However, even though the agent has switched and executed the action 02 stored with ap2, it has not necessarily committed to implementing the entire conditional plan /32- This is because further approximation at k — 1 stages to go may cause it to depart from the implementation of the conditional plans prescribed by the observation strategy 02-Suppose for instance that <J2(z) = /J3. If z is observed, and the agent updates its (approximate) belief state 5(6) accurately to obtain 5(6)', then the maximizing vector at the next stage is necessarily ap3. But given that 5(6)' will be approximated before the maximizing vector is chosen, the agent may adopt some other continuation of the plan if ap3 does not maximize value for the (second) approximated belief state 5(5(6)'). In fact, the agent may implement the conditional plan iS^ = (04,04) of any vector a^4 in the switch set Swk~l(ap3). Notice that the value of the plan actually implemented—doing the action 02 stored with ap2, followed by the action 04 stored with ap4, and so on—may not be represented by any a-vector in 3.2.1 Alt-set computations We can actually construct the values of such plans, and thus obtain much tighter error bounds, while we perform dynamic programming. We recursively define the set of alternative plans, or Alt-set for each vector at each stage. We first define Alt {a) = Swl{a) That is, if a is optimal at stage 1, then any vector in its switch set can have its plan executed. The future alternative set for any ap G where [3 = (a, a), is: FAl1*{aM) = { a { a ^ : (W) aa,{z) G All*'1 (aa(z))} (3.12) 54 If a is chosen to be executed at stage k, true expected value may in fact be given by any vector in FAllfi(a), this is due to future switching of policies at stages following k. Finally, define All* {a) = \J{FAHfi{a') : a' G Sufi (a)} (3.13) If a is in fact optimal at stage k for a given belief state b, but b is approxi-mated currently and at every future stage, then expected value might be reflected by any vector in Alt/*(a). These vectors correspond to every possible course of ac-tion that could be adopted because of approximation: if we switch vectors at stage k, we could begin to execute (the plan associated with) any a' G Sufi (a); and if we begin executing a', we could end up executing (the plan associated with) any a" G FAllfi{c/). Given these Alt-sets, the error associated with belief state approximation is bounded by the maximum difference in value between any a and one of its Alt-vectors. These FAlt and Alt-sets can be computed by dynamic programming while a P O M D P is being solved. Furthermore, the DP procedure to compute them is essentially the same as the incremental pruning DP procedure for N-sets. The con-struction of FAlt-sets and Alt-sets can be decomposed in three steps that are identical to Equations 2.16, 2.17 and 2.18 with the proviso that the sets computed are differ-ent. The first step (Equation 3.14) constructs an intermediary FAlt-set that contains vectors corresponding, roughly speaking, to the expected value of executing action a followed by an alternative plan to CT(Z). The other two steps construct FAlt-sets and Alt-sets as initially defined in Equations 3.12 and 3.13. FAll!°(a{a,a),z) = {^ + 1Ma,za-.a€Altk-1(aa{z))} (3.14) FAl#{a) = ®FAllfi{a,z) (3.15) Allfi{a) = (J FAllfi{a') (3.16) a'eSwk(a) The size of Alt-sets tends to be intractable as it grows exponentially. On 55 — — — Anti-dominated vectors o H — — a - 2 — a . -— 0 ^ b(s) ^ 1 Belief Space Figure 3.4: Lower surface of anti-dominating vectors the other hand, our goal is to derive bounds on the loss in expected return. These bounds are determined by comparing the worst alternative plans to the optimal plan. The worst conditional plans correspond to the vectors that make up the lower surface of an Alt-set. Hence, we can significantly reduce the size of Alt-sets by pruning all anti-dominated vectors (vectors that are dominated from below by one or several other vectors as in Figure 3.4). This is the analog of pruning dominated vectors that are not part of the upper surface of an H-set. Table 3.3 shows an incremental pruning DP procedure to compute an Alt-set at stage k from the 4^ft-sets at stage k — 1. The algorithm is essentially the same as that of Table 2.2 for computing an N-set, with one slight difference: anti-pruning (pruning of anti-dominated vectors) is used instead of pruning. Two important observations can be made concerning the very close similarity of the two algorithms: • Implementation of the DP procedure for 4^^ -sets is easy. Since the incremental pruning DP procedure for tt-sets is fairly straightforward, so is the incremental anti-pruning DP procedure for Alt-sets. Furthermore, their 56 P R O C E D U R E DPaltset{a, k) Alt'{a) <- 0 for each a!(0)0-) € Sufi (a) do FAlifi(aM) <- 0 for each z £ Z do FAllfi(a^a),z) <- antiprune({^ +~/MatZa' : a' £ A f t * - 1 ^ ^ ) ) } ) jR4^(a(QiCT)) <- antiprune{FAHfi(a^a^) © F - A / i ^ a ^ ) , z)) .Aft* (a) <- antiprune(Allfi(a) U Fylft^a^))) return Aft* (a) E N D P R O C E D U R E Table 3.3: Aft-set DP procedure high degree of similarity allows one DP procedure to be generalized with only a few lines of codes to handle both H-sets and Aft-sets. • C o n s t r u c t i n g Aft-sets is a n i n t r a c t a b l e t a s k . The DP procedures for H-sets and Aft-sets are identical from a computational complexity point of view. We already know that solving POMDPs is intractable in general and so will be Alt-set construction. Moreover, at each stage k, one Aft-set is computed per a-vector for a total of \Nk\ Alt-sets, whereas only one K-set needs to be generated. On the other hand, as mentioned in Chapter 2, there is a class of POMDPs , namely the polynomially action-output-bounded P O M D P s , for which the tt-set DP procedure is tractable. One question arises: Is the Aft-set DP procedure for those POMDPs also tractable? The author conjectures that the answer is no. Intuitively, lower surfaces of sets of a-vectors may grow exponentially while their upper surfaces grow polynomially. 3.2.2 Alt-set error bounds Error bounds can be derived from Alt-sets for the cumulative loss in expected total return due to several consecutive approximations. For a fc-stage P O M D P , when the approximation S is used at every time step and a is the maximizing vector for the 57 initial belief state, the cumulative error is bounded by the expression Es(a). This bound can be defined in terms of the vectors in the set All!s(a): Es{a) = max max b-(a-a') (3.17) b^s) a>eAltk(a) Alternatively, since All!°s (a) is the union of the FAlt-sets of each of the vectors in SvJg(a), the bound Eg(a) can also be defined in terms of similar bounds for FAlt-sets, which we denote Fg(a,a'): Fg(a,a') = max max b • (a — a') (3.18) 6eA(5) a„eFAltk(a>) Eks(a) = max F | (a ,a ' ) (3.19) a'eSwk(a) The bounds Eg (a) and Fg(a,a') can be computed using simple pointwise comparison of a with each a' £ Alfs(a) or with each a" G FAlfg(a'). Cumulative approximation error can be bounded globally using: Eks = max Eks{a) (3.20) Furthermore, Eg < Ug since alternate vectors provide a much tighter way to measure cumulative error. Theorem 3 For any k stages to go (k > I), Es < Ug. Proof The proof is by induction. First show that the inequality holds for the base case at one stage to go: Eo = max max max b • (a — a') a e u i beA(s) a,eAlt\a) = max max max b • (a — a') = BS = us Then assume that the inequality holds for k stages to go: Eg < f/| 58 Finally show that the inequality also holds for k + 1 stages to go: max max max max b • (a — a") aeK*+i fceA(s) a,eSwk+1(a) a"eFAltk+1 (a>) max max max max b • (a — a') + b • (a' — a") aenfc+i beA(s) a,eswk+\a) a"eFAltk+\a>) max max max b • (a — a') + max . max max max b • (a' — a") aeN*+l &GA(5) a,eSwk+l(a) a"eFAlf+1 (a>) B k + l + 1 E k s Bks+l + lUks • For an infinite-horizon problem where the optimal set of a-vectors is available, we can compute switch sets once as in the computation of Ug. To compute a tighter bound E*s, we can construct fc-stages of Alt-sets, backing up from H*. Alt1 (a) = Sw*(a) FAlfk(aM) = {a{a^) : (W) aa,{z) € A l ^ 1 {aa(z))} All*(a) = \j{FAl^{a') : a' e Sw*{a)} The bound Ek is computed as for the finite-horizon case (Equations 3.17 and 3.20), and we set Es = E k + 7 k U s (3.21) As for infinite-horizon problems where an e-optimal value function Vk was found, the derivation of an Eg bound appears to be complex. The problem stems from the fact that ^4Ji-sets cannot be computed directly since the set of a-vectors K f c is not available. On the other hand, information about the distance between K f c and itk may provide a way to derive such a bound, as for Ug. In any case, the derivation of an Eg is an open problem. 59 E k + l = < < < 3.3 Value-directed search The B, U and E error bounds derived in the previous section will now be leveraged to design algorithms to search for a good approximation method. The idea is to find an approximation scheme that minimizes those bounds. Unlike the previous section, which was generic in the sense that the bounds derived hold for a wide variety of approximation methods (including projection schemes, density trees and any other linear approximation method), we will now focus on algorithms to search within the class of projection schemes only. Despite their looser bounds (due to their non-linear properties which force us to construct supersets of the switch sets), projection schemes are of great interest since they mesh well with DBNs. Furthermore, as we will see in Section 3.3.1, the class exhibits a nice partial ordering illustrated by a lattice. This lattice turns out to be very useful to guide the search for a good projection scheme. Section 3.3.2 introduces a search algorithm which essentially does a greedy traversal of the lattice. In the previous section, the bounds were derived assuming that the same approximation S was used at every time step and for every belief state. In fact, there was no real need to assume such a uniform approximation since the algorithms work equally well (provide legitimate bounds) when each switch set is computed with a (possibly) different approximation method. Therefore, in this section, we will conduct an independent search to find a good, possibly different, projection scheme for each switch set. Since we have to compute a switch set for each a-vector in the optimal set we will store with each vector a € ft a corresponding projection Sa. At run time, the agent will look up the maximizing vector a for its current belief state b and perform an approximation Sa that simplifies his belief state to Sa(b). The reader may wonder why approximation is needed if it is assumed that the agent knows its current belief state as well as the maximizing vector. As explained in Chapter 2, the state variables that define the belief state tend to become correlated over time; however, in one step, only a few correlations usually creep in. Hence, assuming a 60 projection scheme is used at every time step to break the new correlations as they creep in, one can usually perform an exact belief update on the projected belief state. As a result, the agent can tailor its belief state approximation to provide good results for its currently anticipated course of action. This in turn will lead to much better performance than using a uniform scheme. 3.3.1 Lattice of projection schemes We can structure the search for a projection scheme by considering the lattice of projection schemes defined by subset inclusion. Specifically, we say Si contains S2 (written loosely 52 C Si) if every subset of 52 is contained within some subset of S\. This means that 52 is a finer projection than 5i . The lattice of projections for three binary variables is illustrated in Figure 3.5. Each node represents the set of marginals defining some projection 5. Above each node, the subsets corresponding to its constraining equations are listed (we refer to each such subset as a constraint). The finest projections (which are the "most approximate" since they assume more independence) are at the top of the lattice. Edges are labeled with the subset of variables corresponding to the single constraining equation that must be added to the parent's constraints in order to obtain the child's constraints. It should be clear that if 52 Q Si, then 5i offers (not necessarily strictly) tighter bounds on error when used instead of 52 at any point. Theorem 4 Let 5i and S2 be projection schemes such that S2 C S\ (every marginal of S2 is a subset of some marginal of Si). Then, 1. BkSi < BkS2 2. UkSl < UkS2 (similarly, U*Sl < U*Si) 3. E^ < EkS2 (similarly, E*Si < E*S2) Proof To see this, imagine that various approximation schemes are used for dif-ferent a-vectors at different stages, and that 52 is used whenever a G K f c is 61 62 chosen. If we keep everything fixed but replace 52 with Si at a, we first observe that SwSl(a) C Su/g2(a). This ensures that BSl(a) < Bg2(a) and < Bs . If all other projection operators are the same, then obviously U$ < Ug . Similar remarks apply to the infinite-horizon case. Furthermore, given the definition of Aft-sets, reducing the switch set for a at stage k by using Si instead of S2 ensures that the Aft-sets at all preceding stages are no larger (and may well be smaller) than they would be if S2 were used. For this reason, we have that EkSi < Eg2 (and similarly E*Si < E*g2). • Consequently, as we move down the lattice, the bound on approximation error gets smaller (i.e., our approximations improve, at least in the worst case). Of course, the computational effort of monitoring increases as well. The precise computational effort of monitoring will depend on the structure of the D B N for the P O M D P dynamics and its interaction with the marginals given by the chosen projection scheme; however, the complexity of inference (i.e., the dominant factors in the corresponding clique tree), can be easily determined for any node in the lattice. 3.3.2 Greedy search In a P O M D P setting, the agent may have a bounded amount of time to make an online decision at each time-step. For this reason, efficient belief-state monitoring is crucial. However, just as solving the P O M D P is viewed as an offline operation, so is the search for a good projection scheme. Thus it will generally pay to ex-pend some computational effort to search for a good projection scheme that makes the appropriate tradeoff between decision quality and the complexity of belief state maintenance. For instance, if any scheme 5 with at most c constraints offers ac-ceptable online performance, then the agent need only search the row of the lattice containing those projection schemes with c constraints. However, the size of this row is factorial in c. So instead we use the structure of the lattice to direct our attention toward reasonable projections. 63 We describe here a generic, greedy, anytime algorithm for finding a suitable projection scheme. We start with the root, and evaluate each of its children. The child that looks most "promising" is chosen as our current projection scheme. Its children are then evaluated, and so on; this continues until an approximation is found that incurs no error (specifically, each switch set is a singleton) or a threshold on the size of the projection is reached. We assume for simplicity that at most c constraints will be allowed. The search proceeds to depth c — n in the lattice and at each node, at most nc children are evaluated, so a total of 0(nc2 — cn2) nodes are examined. Since c must be greater than n—the root node itself has n constraints—we assume 0(nc2) complexity. The structure of the lattice ensures that decision quality (as measured by error bounds) cannot decrease at any step. We note that non-practical projections (projections for which we cannot construct a clique tree) are included in the lattice. In Figure 3.5, the only non-practical scheme is S = {AB, AC, BC}. During the search, it doesn't matter if a node corresponding to a non-practical scheme is traversed, as long as the final node is practical. If it is not practical, then the best practical sibling of that node is picked or we backtrack until a practical scheme is found. We also note that since this is a greedy approach, we may not discover the best projection with a fixed number of constraints. However, it is a well-structured search space and other search methods for navigating the lattice could be used. We now describe an instantiation of this algorithm whereby the 5-bound at a given stage k is minimized. We will later build on this basic search procedure to develop algorithms that minimize the U and E bounds of finite and infinite-horizon problems. Given a collection of a-vectors we run the following search independently for each vector a E H 4 , The order does not matter; we will end up with a projection scheme S for each a-vector, which is applied whenever that a-vector is chosen as optimal at stage k. We essentially minimize (over S) each term Bs(a) in the bound Bk independently. For a given vector a, the search proceeds 64 from the root in a greedy fashion. Each child S of the current node is evaluated by computing Bs(a), which basically requires that we compute the switch set Su;5(a), which in turn requires the solution of |N f c | LP-switch tests. Once the projection schemes Sa for each a are found, the error bound Bk is given by the maximum bound Bk(a) as described in the previous section. The number of LPs that must be solved is 0(nc 2 |N f c | 2 ) since there are 0(|H f c|) a-vectors and for each a-vector, the lattice search traverses 0(nc 2) nodes, each requiring the solution of 0(|N f c|) LPs. The above algorithm can be streamlined considerably. At a given node, when computing the bound Bg(a), it is not necessary to generate the entire switch set of a. Each vector a' £ Hk, if switched to, introduces an error of at most max;, b-(a-a'). Since Bg(a) = maxa,egwk^ m&*-b b- (a — a'), we can test vectors a' in decreasing order of contributed error until one vector is found to be in the switch set. The bound Bg(a) is equal to the error contributed by this vector. As a result, instead of solving LPs to determine the bound Be;(a) of each node visited, generally, only a few LPs need to be solved. The number of LPs can be further reduced by observing that any a-vector that is not in the switch set of a node won't be in the switch set of any of its children nor descendants. This is because descendants possess constraints that form a superset of this node's constraints. Thus, at any child, we can avoid computing the LP-switch tests for the vectors that are'known not to be in that node's switch set. When those two techniques are combined, one can show that the number of LP-switch tests to be performed at each node is on average a small constant, which reduces the overall complexity of finding good projection schemes for each a-vector in H f e to 0(nc2\^k\). There is another possible speed-up. When testing whether two different schemes Si and S2 allow switching to some a-vector, the LPs to be solved for each scheme are similar, differing only in the constraints dictated by each projection scheme. This similarity can be exploited computationally by using techniques that take advantage of the numerous common constraints if we solve similar LPs "con-65 currently" (for instance, by solving a stripped down L P that has only the common constraints and using the dual simplex method to account for the extra constraints). Though details are beyond the scope of this thesis, from experience, these techniques tend to be faster in practice than solving each L P from scratch. The greedy search can take full advantage of these techniques: each child has only one additional con-straint (compared to its parent), so not only can structure be shared across children, but the parent's solution can be exploited as well. This computational trick could potentially reduce the worst-case running time to 0(nc|N f c|) LPs. Further theoretical and practical investigation remains to be done. The above .B-bound search algorithm has a running time of 0{nc21Kfc|) LPs (or perhaps only 0(nc|tt f c|) LPs) whereas the Hfc-set DP procedure must solve at least $l(|ttfc|) LPs. When integrating the -B-bound search algorithm to the DP procedure for computing N*, the overhead incurred is at most a multiplicative factor nc 2 (or perhaps only nc). Although the usual sources of intractability (large state space and large N-sets) limit the applicability of this search algorithm, it can be applied to POMDPs that can be readily solved today, since the overhead incurred is not too significant. To conclude this chapter, a brief description of algorithms that extend the .B-bound search to [/-bounds and i£-bounds is presented. • Finite-horizon [/-bound search: The [/-bound for a A;-stage P O M D P is the discounted sum of the 5-bounds for each stage. Hence, it suffices to minimize each .B-bound in order to minimize the [/-bound. Therefore, the search consists of k .B-bound searches, one for each set W (1 < i < k). • Infinite-horizon optimal [/-bound search: Similarly the bound U* is minimized when the bound B* is minimized. Thus, the search boils down to one -B-bound search for the set N*. • Infinite-horizon e-optimal [/-bound search: Once again, the upper bound 66 (Bk + fj,)/(l — 7) is minimized when B is minimized and therefore a single S-bound search is conducted for the set Finite-horizon E'-bound search: The bound Ek is minimized when the bounds Ek(a) are minimized for each vector a G In turn, using Equa-tion 3.19, the bound Ek(a) is minimized when the switch set Sufi (a) contains vectors a' with corresponding error bounds Fk(a, a') that are as small as pos-sible. Hence one can conduct an i?-bound search in the same way than a in-bound search with one slight modification: at each node, select the child with the most promising (smallest) E'-bound. At i stages to go of a A;-stage P O M D P , the agent would first construct the FAlt-sets of each vector a G Then the agent would search a good projection scheme for each vector a G N \ As for the .B-bound search, the lattice is traversed in a greedy fashion. At each node 5, the corresponding switch set SuJg(a) is constructed and the bound Eg (a) is simply the worst bound Fg(a,a') for some vector a' G Su/g(a). Once the projection searches are completed, the Aft-set of each vector is constructed and the process starts over for the previous stage until k stages to go. Infinite-horizon optimal E?-bound search: According to Equation 3.21, the bound E* is minimized when both bounds Ek and U* are also minimized. Therefore, the search consists of A; consecutive .E-bound searches for the set H*. We should also conduct a .B-bound search for H* (to minimize U*); however, this .B-bound search is identical to the first E'-bound search and therefore redundant. In practice, the projections applied would be those found during the kth S-bound search. 67 Chapter 4 Vector Space Analysis The value-directed framework introduced so far has allowed us to analyze the im-pact of approximate belief state monitoring on decision quality. This analysis was conceptually simple and remained at a fairly high level. The idea was simply to look at all the possible courses of action as a result of one approximation (switch set) or several consecutive approximations (Alt-set) and to derive several bounds, which, roughly speaking, measure the loss in expected total return assuming the worst pos-sible course of action (we could switch to) was implemented. In turn, these bounds have allowed us to structure the class of projection schemes in a lattice, which can be traversed greedily to find a fairly good projection. From a decision theoretic point of view, this may all seem pretty satisfying, but from a practical perspective, the algorithms are generally intractable and from a conceptual perspective, the frame-work provides little insight as to which properties of projection schemes cause or prevent plan switching. In order to provide some insights, this chapter analyzes approximation meth-ods from a linear algebra perspective. More precisely, a vector space analysis is car-ried out. Appendix A provides an overview of some of the basics of linear algebra that will be useful for the development of the current chapter. Section 4.1 reveals that each projection scheme allows approximations only in some directions defined 68 by a subspace. On the other hand, a similar analysis of the value function shows that a-vectors can determine "gradients" indicating the variability of the value function in different directions. Therefore, approximations in directions where the variance is similar for most a-vectors should be preferred since switching is less likely to happen. From a practical perspective, these observations will be used in Section 4.2 to design faster algorithms than those proposed in Chapter 3, however yielding looser bounds. The LP-switch test introduced so far took into account approximation distance and direction. The idea will be to relax this L P to focus mainly on direction. As a result, the simplified switch test has an efficient solution algorithm that does not require an L P anymore. Finally, Section 4.3 presents a vector-space search algorithm. It differs from previous value-directed search algorithms as it doesn't aim to directly minimize any error bound. Rather, it seeks a projection scheme that allows approximations in directions where a-vectors have a similar variance. 4.1 Vector space formulation Given a projection 5, let b and b' — S(b) be points in belief space. Define d = b' — b as the displacement vector that goes from b to b'. We are about to show that all such displacement vectors are part of a special subspace that is entirely determined by the projection S. A subspace is an important concept that allows us to characterize the possible directions of displacement vectors. The subspace determined by a projection is actually defined by its marginals. For instance, assume a state space defined by the binary variables X and Y. Pro-jection S = {X, Y} determines a set of linear equations constraining the probability distribution b' in terms of b. These equations are the same as those of the form 69 b(M) = b'(M) in Table 3.2. b(xy) + b(xy) + b(xy) + b(xy) — b'(xy) + b1 (xy) + b'(xy) + b'(xy) b(xy) + b(xy) = b'{xy) + b'(xy) b(xy) + b(xy) = b'(xy) + b'{xy) Using the fact that d = U — b, the above equations can be rewritten in terms of displacement vectors as follows: d(xy) + d(xy) + d(xy) + d(xy) = 0 (4.1) d(xy) + d(xy) = 0 (4.2) d{xy) + d(xy) = 0 (4.3) Geometrically, we can interpret each equation as a hyperplane and the in-tersection of those hyperplanes is a line through the origin representing a one-dimensional subspace (an example is given below to illustrate the resulting sub-space). This subspace, which corresponds to the equations' solution space, captures the set of all displacement vectors resulting from the application of 5. Since all possible displacement vectors lie on the same line, they must all have the same direction. Here, vectors with opposite orientations are assumed to have the same direction. To illustrate, let b(x) = 0.3 and b(y) = 0.4. The approximate belief state, assuming the correlation between X and Y is broken, is computed as follows: b'(xy) = b{x)b(y) = 0.12 b'(xy) = b(x)(l-b(y)) =0.18 b'(xy) = (1 - b{x))b{y) = 0.28 b'(xy) = (l-b(x)))(l-b(y))=0A2 Figure 4.1 shows a three-dimensional belief space for belief states xy, xy, xy 70 and xy.1 Al l exact belief states b that satisfy b(x) = 0.3 lie in a hyperplane and similarly for b(y) = 0.4. Their intersection is the line of exact belief states that are mapped to b' by S. Since b' also lies on this line, then all the displacement vectors between b and b' have the same direction. Had we picked marginals different than 0.3 and 0.4, the hyperplanes would move, but remain parallel, and so would their intersection, yielding a line with the same direction. Definition 1 Let Ds be the subspace spanned by the set of all displacement vectors possibly induced by projection scheme S. In general, the set of displacement vectors induced by a projection S lies in a (2™ — c)-dimensional subspace, which we denote Ds- Here n is the number of state variables and c is the number of constraints (or marginals). Ds has 2" — c dimensions since it is the solution space of c linearly independent equations, each corresponding to a constraint d(M) = 0. Equations 4.1, 4.2 and 4.3 are examples of constraints of the form d(M) — 0 for M = 0, M = X and M = Y respectively. 1Only three dimensions corresponding to b(xy), b(xy) and b(xy) are represented since b(xy) follows from the fact that probability distributions sum up to 1. 71 Those equations are linearly independent since the marginals M in each constraint correspond to different subsets of variables. This becomes more obvious when we rewrite each equation d(M) = 0 as a dot product • d = 0. Here VM is a vector of 0's and l's, such that every component set to 1 corresponds to a state with all variables in M set to true, and every component set to 0 corresponds to a state with at least one variable in M set to false. The following three vectors correspond to the marginals determined by the projection S = {X, Y}. xy xy xy xy t>0 = ( 1 1 1 1 ) vx = ( 1 1 0 0 ) Vy = ( 1 0 1 0 ) Definition 2 Let Dg be the subspace spanned by the vectors VM corresponding to the marginals defined by projection scheme S. The subspace Dg is closely related to Dg since it is its null space, or in other words, Dg is the set of all vectors perpendicular to every vector in Ds. Proposition 1 Dg is the null space of Dg. Proof Two vectors are perpendicular to each other when their dot product is 0. Since VM • d — 0 for all vectors that span Dg and for all displacement vectors d that span Dg, it follows that all vectors in Dg are perpendicular to every vector in Dg. Similarly one can show that all vectors perpendicular to Ds are in Dg. • 4.2 Vector space switch test The subspaces Dg and Dg are very important as they allow us to design a simplified switch test. Let's say we are interested to know if aj £ Sw(ai). Define to be a vector representing the difference in expected value for executing aj instead 72 of ai. When € Dg, we can show that there is no switch from ai to aj. On the other hand, if aij ^ Dg, there may be a switch. Thus, based on whether is in Dg or not one can construct a superset of the switch set. The idea behind the vector space (VS) switch test, is best explained by a picture. Figure 4.2 shows a top down view of a two dimensional belief space2 with two different partitions. The first partition is given by the solid lines which define |N| regions, each corresponding to the area Ra for each vector a £ H . The second partition is given by the dotted line which separates two regions corresponding to the areas where ai dominates aj and vice-versa. Let's denote those areas Rai and Raj • The LP-switch test, as defined in Section 3.1, verifies if there exists a belief state 6 G Rai such that S(b) G R a j . Alternatively, a VS-switch test verifies if there exists a belief state 6 G Rai such that S(b) G R a j . Below, Theorem 5 shows that when a VS-switch test is negative (that is, there doesn't exist any belief state b G Rai such that S(b) G Raj), the corresponding LP-switch test is also negative and therefore aj ^ Sw(ai). The reverse is not true, so a positive VS-switch test only indicates that aj may be in Sw(ai). Theorem 5 / / —>36 G Rai such that 5(6) G Raj, then -i36 G Rai such that S(b) G Rar Proof Let's show that the converse holds, that is, if 3b G Rai such that 5(6) G Raj, then 36 G Rai such that 5(6) G Raj • It should be fairly obvious that Rai C Ra. since Rai corresponds to the area where a, dominates all other vectors in N and Rai correponds to the region where CVJ dominates aj. By the same argument, Raj is also a subset of Raj. Thus, when there is a belief state 6 G Rai such that 5(6) G R a j , then 6 is also in Rai and 5(6) is also in Raj • The optimization program corresponding to a VS-switch test is given in Ta-ble 4.1. This optimization program is essentially the switch test program of Table 3.1 2 There are 3 states si, S2 and S3 but only two dimensions are necessary since probability distributions sum up to 1. 73 max x s.t. b • (ai — aj) > x 5(6) • (aj — ai) > x Zsb(s) = l b(s) > 0 Vs Table 4.1: VS-switch test for projection schemes. The optimization program has a strictly positive objective function when there exists a belief state 6 £ Rai such that 5(6) G Raj and a non-positive objective function where there doesn't exists such a belief state. with the exception that all the constraints involving a-vectors other than a^ and aj have been removed. Since projection schemes yield non-linear approximations, we can define a linear VS-switch test as in Table 4.2. This L P is a relaxation of the L P switch test of Table 3.2. As demonstrated in Theorem 1 for LP-switch tests, linear VS-switch tests can be used to construct supersets of the switch sets obtained by a non-linear VS-switch tests. For practical reasons, we will consider from now on exclusively the linear version of VS-switch tests and we will refer to them simply as VS-switch tests. 74 max x s.t. b • (ai — aj) > x b' • (aj — a^ > x b'(M) = b(M) VMCMul<l<n Tsb{s) = l b(s) > 0 Vs b'(s) > 0 Vs Table 4.2: Linear VS-switch test for projection schemes. This L P has a strictly positive objective function when there exists belief states b G Rai and b' £ Raj such that b(M) = b'(M) for all marginals M defined by projection 5 and a non-positive objective function when there doesn't exist such belief states. We will now show how a (linear) VS-switch test is equivalent to verifying whether Dg contains a^ or not. More precisely, the VS-switch test is positive when aij Dg and negative when a^ G Dg. The idea is to consider aij as a gradient that measures the error induced by an approximation when comparing the expected total return of ai to aj. Recall that the vector a^ measures the difference in expected total return between a, and aj. After an approximation, if this difference changes considerably, the agent is likely to choose the wrong maximizing a-vector. Let's call relative error this change in the relative assessment of aj with respect to aj. Formally, the relative error is quantified as follows: relative error = 6(aj — aj) — S(b)(ai — aj) = b • a^ - S(b) • a^ = d-aij (4.4) Here a%j can be viewed as a gradient since approximations corresponding to a displacement vector d in the same direction as a^ (parrallel to a^) maximimize the magnitude of the dot product d-aij. In general, the angle between d and a^ is a good indicator of approximation error. In particular, if they are perpendicular, their dot product is zero and the relative assessment of ai and aj remains unchanged, preventing any switch. By definition, the subspace Dg is the set of vectors perpen-75 dicular to all displacement vectors possibly induced by S, so when a^ is a member of Dg, all possible displacement vectors are perpendicular to and consequently there cannot be a switch from ai to aj. Below, Theorem 6 gives a formal proof of the equivalence between the VS-switch test and the subspace membership test "is a%j e Theorem 6 There exists no 6 G Rai,b' G Raj such that b'(M) = b(M) for all marginals M defined by S iff a^ G Dg. Proof First, suppose that 3b G Rai,b' G Raj such that b'(M) = b(M) for all marginals M defined by S, let's show that a^ fi Dg. Since b G Rai then b • (ai — aj) > 0. Similarly, because b' G Raj it follows that —6' • (ai — aj) > 0. If we add those two inequalities together, we get (b — b1) • (ai — aj) = d-a^ > 0. By definition, a^ G Dg iff d- = 0 Vd G Dg, so a^ is not an element of Dg. Next, suppose that a^ ^ Dg, then let's show that 3b G R a i , b' G Raj such that b'(M) = b(M) for all marginals M defined by S. Since a^ Dg, then there exists a displacement vector d G Dg such that d-a^ ^ 0. W L O G let d-a^ > 0.3 For any sufficiently small vector d G Dg, there exist 6 G Rai,b' G i ? a j such that d = 6 -6 ' . Finally, since d £ Dg, then by definition rf(M) = 0 V M and consequently 6(M) = 6'(M) V M . • Although we could use the L P in Table 4.2 to carry out VS-switch tests, there is a much more efficient method based on the subspace membership criteria. The idea is to decompose a^ in two orthogonal vectors corresponding to the projections of a^ on Dg and Dg. Below, proj(a,D) stands for the projection of the vector a on the subspace D. a^ = proj(aij,Dg) + proj(aij,Dg) (4.5) If G Dg, then proj(aij,Dg) = a^ and consequently proj(aij,Dg) is the zero vector; otherwise, proj(aij,Dg) / a^ and consequently proj(aij,Dg) 3If d • < 0, then pick d' = —d since — d • > 0. 76 is a non zero vector. Based on this observation we can determine if aij G Dg by measuring the length of proj(aij,Ds): \\proj(aij,Ds)\\2 = 0 when a^ G Dg, and \\proj(otij,Ds)\\2 > 0 when a^ fi Dg. In particular, the squared length of proj(ctij, Dg) can be computed by the following equation: \\proj(aij,Ds)\\2 = ctij • - E ( a u ' v ) 2 ( 4 - 6 ) Here Vg is an orthonormal basis spanning the subspace Dg. Theorem 7 shows how to derive the above expression. Theorem 7 Let Vg be an orthonormal basis spanning the subspace Dg, then \\proj{aij,Ds)\\l = • a^ - E (o^ • v)2 Proof \\proj(aij,Ds)\\22 = WaaWl-WproJia^D^Wl (4.7) — aij • aij E ProJictij^W* (4.8) = aij-aij~ E \\ProJ(aij^v)\\2 (4-9) — (Xij * O-ij E K ^ ) 2 (4-io) Equation 4.7 follows since Ds and Dg are complementary orthogonal sub-spaces. In Equation 4.8, a projection on a subspace is equivalent to the sum of the projections on each vector of an orthonormal basis of this subspace. In Equation 4.9, the squared length of a sum of orthogonal vectors is the sum of the squared length of each othogonal vector. Finally, in Equation 4.10, the squared length of the projection of a^ on some unit vector v is by definition the squared dot product of a^ and v. • In order to compute expression 4.6, we need an orthonormal basis that spans the subspace Dg. A n orthonormal basis is a basis with two special properties: all 77 its vectors are normal (length equal to one) and pairwise orthogonal (perpendicular to each other). In general, any spanning set of vectors can be transformed into an orthonormal basis by applying the Gram-Schmidt orthogonalization process and normalizing the resulting vectors. The subspace Dg was originally defined by the spanning set of vectors VM corresponding to the constraint for each marginal M, hence this set can be used to generate several orthonormal bases. In this thesis, we shall consider one orthonormal basis in particular—which we will refer to as Dg— because of its factored representation. For problems involving binary variables, every vector in our choice of Vg consists o f a sequence of l's and —l's (before normalization). The basis vector VM associated with subset M has a 1 in every component corresponding to a state with an even number of true variables in M and —1 in every component corresponding to a state with an odd number of true variables in M. The vector is then normalized by dividing by ^/\S~\. For instance, projection scheme S = {XY,YZ} has six marginals (0, X, Y, Z, XY and YZ), yielding the following basis vectors:4 xyz xyz xyz xyz xyz xyz xyz xyz { 1 1 1 1 1 1 1 1 vx = ( - 1 -1 -1 -1 1 1 1 1 Vy = ( -1 -1 1 1 -1 -1 1 1 VZ = ( -1 1 -1 1 -1 1 -1 1 VXY = ( 1 1 -1 -1 -1 -1 1 1 VyZ = ( 1 -1 -1 1 1 -1 -1 1 ) / ) / ) / ) / ) / ) / •51 W\ We now have all the necessary information to carry out very efficient VS-switch tests. The running time of such switch tests is much lower than that of LP-switch tests. A VS-switch test boils down to the computation of Expression 4.6 which requires 0(c) dot products. In turn, each dot product requires 0(|5|) ele-mentary operations, for a total running time of 0(c|«S|) . The use of factored repre-4This definition of Vg can be generalized to non-binary variables. 78 sentations such as ADDs improves considerably this running time. More precisely, each basis vector has components that take only two values, yielding a very compact A D D representation. The number of operations required to compute the dot prod-uct of two factored vectors is essentially linear in the size of the intersection of their A D D representation. The basis vectors have a very small A D D representation since every state takes one of two possible values. Similarly, the vector also has a small A D D representation since we assume that the P O M D P is fairly structured. Thus, the number of operations for a dot product is often a small constant independent of the size of the state space. Hence, for sufficiently structured POMDPs , the effective running time of a VS-switch test tends to be 0(c). In comparison, solving the linear program of an LP-switch test is polynomial in the number of constraints c and the size of the state space. Furthermore, ADDs do not provide a speed up as important for LPs since the effective state space is the intersection of the abstract state space of all the constraints instead of only two vectors for dot products. In particular, as explained in Section 3.1, LP-switch tests for projection schemes do not benefit at all from ADDs. Hence, VS-switch tests provide a much more efficient and practical method to compute switch sets. On the other hand, this efficiency gain results from the use of relaxed constraints, which means that the switch set computed is really a superset. In turn, this has an impact on the quality of the B, U and E bounds since they will be looser, however the algorithms to compute them remain unchanged. The running time of the greedy lattice search when using VS-switch tests is significantly improved. With LP-switch tests, it was 0(nc2|ft|) LPs (or 0(nc 2 + f c|H||<S| f e) elementary operations, assuming an L P requires a number of operations that is a polynomial of degree k in terms of c and |<S|) whereas with VS switch tests, it is 0(nc3|H||<S|) elementary operations. Note here that the upper bounds on running times are given in terms of the size of the full state space |<S| since there are prob-lems for which factored representations do not provide any savings, however, the 79 reader should keep in mind that in practice, many P O M D P s are structured and al-low ADDs (for instance) to reduce their effective state space considerably (possibly linear in the number of variables instead of the number of states). 4.3 Vector space search In this section, we describe an alternative search method based on the relative error (expression 4.6). We call it the vector-space search or in short the VS search. It differs from the previous .B-bound search and E'-bound search in that it doesn't try to minimize an error upper bound. The fact is that in practice, minimizing the worst possible error doesn't necessarily lead to good average results. The basic idea behind the VS search is rooted in the observation that the more perpendicular is the direction of an approximation with respect to a^, the smaller is the magnitude of the relative error and consequently, the less likely a switch will occur. Thus, the VS search, seeks a projection S which defines a dis-placement subspace Ds that is as perpendicular as possible to all gradients a^. Technically, this is done by minimizing the squared length of the projection of each gradient on Ds (as in Equation 4.6). It is interesting to note that the length of proj(atj,Ds) has a special in-terpretation: it corresponds to the greatest (absolute) relative error rate for an approximation in some direction d £ Ds- The relative error rate for an approxi-mation corresponding to the displacement vector d, is given by the relative error induced by a unit displacement in the direction of d: d By definition, the projection of a vector a on some subspace D is: \\proj{a,D)\\2 = sup | T - ^ - • a\ d£D \\d\\2 Hence, by minimizing expression 4.6, we are essentially minimizing the (squared) worst relative error rate that may occur as a result of some projection S. When 80 ignoring the distance between the exact and approximate belief states, the relative error rate gives us a handle to quantify how bad an approximation in some direction is likely to be. Each projection S constrains approximations to directions within the subspace Ds- The direction d € Ds with the highest (absolute) relative error rate is this worst relative error rate which also happens to be \\proj(aij,Ds)\\2- Thus, it makes sense to try to minimize expression 4.6. When searching for a good projection S for belief space region Rai, there are |H| — 1 a-vectors we would like to prevent switching to. Ideally this would be accomplished by minimizing simultaneously expression 4.6 for every gradient (j ^ i). In the absence of any prior concerning the relative importance of each gradient, we suggest two simple schemes: • Minimize the sum of the squared length of each projection: E \\proj(aij,Ds)\\2 = Y,(av ' «v ~ zZ v ' ««) (4-n) • Minimize the squared length of the greatest projection: max \\proj(aij,Ds)\\l = max (a -^ • - Y] v • a^) (4.12) Of course, many other schemes could be proposed and if the practitionner has some prior knowledge, it should definitely be used. Given a vector aj € H, the VS search finds a good projection S as follows. Starting at the root, traverse the lattice downwards in a greedy manner. At each node, pick the most promising child by minimizing Equation 4.11 or Equation 4.12. The computational complexity of a VS search is fairly low as it avoids LPs. Its running time is 0(nc 3|N| 2|(S|), since one good projection must be found for each of the |N| regions Ra. For each region, 0(nc2) nodes in the lattice are traversed, each requiring the evaluation of Equation 4.11 or 4.12 which both take 0(c|N||<S|) elementary operations. 81 As with the 5-bound and E-bound search procedures, the VS search can also be streamlined but in a different way. The constraints of a node S are essentially the same as the constraints of its parent node S' with one extra constraint corresponding to the marginal M that labels the edge connecting the two nodes. Since there is one basis vector per constraint, the following equation holds: = Vj, U {vM} In turn this means that Equations 4.11 and 4.12 can be computed incremen-tally as the lattice is traversed downwards: Y \\proj(aij,Ds)\\2 = Y \\Pr°J(aij'DS')\\2 ~ VM • ctij max \\proj(aij,Ds)\\l = max \\proj(aij, DS>)\\1 - • aij 3fr 3fr Incremental computation reduces the running time to 0(nc 2|H| 2|(S|) since only one dot product needs to be computed instead of one for each of the c con-straints. This running time is significantly smaller than 0(nc2 + f c|^||<S| f c) for the .B-bound or E-bound greedy search with LP-switch tests. As for the .B-bound or E-bound greedy search with VS-switch tests, the running time 0 ( n c 3 i s com-parable. The VS search has an extra |H| factor, but one less c factor. In practice, |N| is usually larger than c, so the VS search is actually slower. Again, the reader should keep in mind that the upper bounds on running times are given in terms of but in practice, factored representation can drastically reduce the size of the effective state space for structured POMDPs. 82 Chapter 5 Empirical Evaluation This chapter evaluates empirically the algorithms proposed so far. First, in Sec-tion 5.1, the factory example introduced in Chapter 1 is revisited with specific transition probabilities and reward functions. We show how a value-directed ap-proach yields a better choice of projection schemes than distance based approaches that try to minimize the KL-divergence, L\ or L2 norms. The experiments carried out with this factory example are very simple and serve only as a proof of concept. In Section 5.2, more extensive experiments are carried out to evaluate the quality of the approximation algorithms as well as their running time. The reader should be warned however that those experiments are still limited in scope and complexity, and may not be representative of typical real world problems. This is because we are not yet in a position to solve large interesting POMDPs . Therefore the three problems used to carry out the experiments are simple and fairly structured so that the number of a-vectors representing a value function remains manageable and the representation of each a-vector can be factored and made compact. The goal of these experiments is threefold: • Compare the running time of different search algorithms. • Compare the B, U and E error bounds, which measure the expected loss in a worst case scenario, to the average loss realized for 5000 random policy 83 executions. • Compare the average loss due to projections obtained by different search al-gorithms. Note that those experiments do not evaluate the belief state monitoring speed up obtained by the application of different projection schemes. This is because the focus of this thesis is on approximation quality which had not been investigated thoroughly in the literature. The reader is referred to Boyen and Koller [3] for experiments illustrating the speed up obtained by projection schemes. 5.1 Proof of Concept Let's revisit the factory problem described in Section 1.2 to illustrate the benefits of value-directed approximation. The aim is to demonstrate that minimizing belief state error as measured by KL-divergence, L\ or Li norms is not always appropriate when approximate monitoring is used to implement an optimal policy. Below, the factory problem is made concrete through a process involving seven stages, with only one or two actions per stage (thus at some stages no choice needs to be made), and no observations. Yet, even such a simple system shows the benefits of allowing the value function to influence the choice of approximation schemes. We suppose there is a seven-stage manufacturing process whereby four parts are produced using three machines, M, Ml, and M2. Parts Pl, P2, P3, and P4 are each stamped in turn by machine M. Once stamped, parts Pl and P2 are processed separately (one after the other) on machine Ml, while parts PS and P4 are processed together on M2. Machine M may be faulty (FM), with prior probability Pr(FM). When the parts are stamped by M, parts Pl and P2 may become faulty (FI, F2), with higher probability of fault if holds. Parts P3 and P4 may also become faulty (F3, F4), again with higher probability if FM; but F3 and F4 are both less sensitive to F M t h a n FI and F2 (e.g., Pr(Fl\FM) = Pr(F2\FM) > Vv(F3\FM) = Pr(F4\FM)). 84 Stages to go Actions Transitions Rewards 7) Stamp P l Stamp P l only affects FI if F M at previous step then Pr(Fl) = 0.8 else Pr(Fl) : no reward 0.1 6) Stamp P2 Stamp P2 only affects F2 if F M at previous step then Pr(F2) = 0.8 else Pr(F2) = 0.1 no reward 5) Stamp P3 Stamp P3 only affects F3: if F M at previous step then Pr(F3) = 0.1 else Pr(F3) = 0.05 no reward 4) Stamp P4 Stamp P4 only affects F4: if F M at previous step then Pr(F4) = 0.1 else Pr(F4) = 0.05 no reward 3) Process/Reject P l Process P l Reject P l all variables are persistant all variables are persistant i f F l then 0 else 8 4 for every state 2) Process/Reject P2 Process P2 Reject P2 all variables are persistant all variables are persistant if F2 then 0 else 8 4 for every state 1) Process/Reject P3,P4 Process P3.P4 Reject P3,P4 all variables are persistant all variables are persistant i fF3&F4then -2000 if ~F3 & ~F4 then 16 otherwise 8 3.3 for every state Table 5.1: P O M D P specifications for the factory example If Pl or P2 are processed on machine Ml when faulty, a cost is incurred; if processed when O K , a gain is had; if not processed (rejected), no cost or gain is had. When PS and P4 are processed (jointly) on M3, a greater gain is had if both parts are O K , a lesser gain is had when one part is O K , and a drastic cost is incurred if both parts are faulty (e.g., machine M 3 is destroyed). The specific problem parameters are given in Table 5.1. Figure 5.1 shows the dependencies between variables for the seven-stage D B N of the example.1 It is clear with three stages to go that all the variables are corre-lated. If approximate belief state monitoring is required for execution of the optimal x We have imposed certain constraints on actions to keep the problem simple; with the addition of several variables, the problem could easily be formulated as a "true" D B N with identical dynamics and action choices at each time slice. 85 Figure 5.1: DBN for the factory example policy (admittedly unlikely for such a simple problem!), a suitable projection scheme could be used. Notice that the decisions to process PI and P2 for 3 or 2 stages-to-go are independent: they depend only on PT(F1) and Pv(F2), respectively, but not on the correlation between the two variables. Thus, though these become quite strongly correlated with five stages to go, this correlation can be ignored without any impact on the decision one would make at those points. Conversely, F3 and F4 become much more weakly correlated with three stages to go; but the optimal decision at the final stage does depend on their joint probability. Were we to ignore this weak correlation, we run the risk of acting suboptimally. We ran the i?-bound search algorithm (with LP-switch tests) of Section 3.3 and, as expected, it suggested projection schemes that break all correlations except for FM and FS with four stages to go, and F3 and F4 with three, two, and one stage(s) to go. The latter, Pr(F5, F4), is clearly needed (at least for certain prior probabilities on FM) to make the correct decision at the final stage; and the former, Pr(FM, F S ) , is needed to accurately assess Pr(F5, F4) at the subsequent stage. Thus 86 Correlation Li L2 KL Loss F1/F2 0.7704 0.3092 0.4325 1.0 F3/F4 0.9451 0.3442 0.5599 0.0 Table 5.2: Comparison of different distance measures we maintain an approximate belief state with marginals involving no more than two variables, yet we are assured of acting optimally. In contrast, if one chooses a projection scheme for this problem by minimiz-ing KL-divergence, Li-distance, or ./^-distance, different correlations will generally be preserved. For instance, assuming a uniform prior over FM (i.e., machine M is faulty with probability 0.5), Table 5.2 shows the approximation error that is in-curred according to each such measure when only the correlation between FI and F2 is maintained or when only the correlation between F3 and F4 is maintained. Al l of these "direct" measures of belief state error prefer the former. However, the loss in expected value due to the former belief state approximation is 1.0, whereas no loss is incurred using the latter. To test this further, we also compared the approxima-tion preferred using these measures over 1000 (uniformly) randomly-generated prior distributions. If only the F i /F£ -corre la t ion is preserved with one stage to go, then in 520 instances a non-optimal action is executed with an average loss of 0.6858. This clearly demonstrates the potential advantage of using a value-directed method to choose good approximation schemes. 5.2 Experiments Three test problems were used to carry out the more extensive experiments. The first P O M D P is essentially the coffee problem introduced by Boutilier and Poole [2]. The second P O M D P is a variation of the widget problem described by Draper, Hanks and Weld [10]. The third P O M D P is inspired from the pavement maintenance problem described by Puterman [32]. Since the analysis of the experiments doesn't require 87 Problem State Space Size Size of N Solution Time full effective maximum average (sec) Coffee 32 12 102 56 47 Widget 32 14 205 121 397 Pavement 128 85 39 16 250 Table 5.3: Solution statistics for the three test problems any specific domain knowledge, the exact specifications of these three problems can be found in Appendix B. Before getting into the details of the experiments, it is important to point out a few statistics regarding each test problem. Table 5.3 shows the solution time to find an optimal solution for a discounted finite-horizon of 15 steps. In fact, all the experiments that follow assume a finite discounted horizon of 15 steps (unless otherwise stated). In the table are also included the size of the state space as well as the average and maximum number of a-vectors necessary to represent the optimal value function at each of the 15 stages. We remind the reader that the size of the state space and the number of a-vectors are critical features"of a P O M D P that have a direct impact on the solution time, as well as the algorithms proposed in this thesis. The state space column is divided in two: the full state space corresponds to |K| and the effective state space is the largest intersection of abstract state spaces encountered in an LP-dominance test. Since all algorithms were implemented using ADDs, their running time depends on the size of the effective state space rather than the full state space, with one exception, LP-switch tests. As explained in Section 3.1.1, LP-switch tests do not benefit from ADDs since the intersection of all abstract state spaces (corresponding to A D D representations of the constraints defined by a projection scheme) is the full state space. 88 Problem Solution Time .B-bound search .E-bound search VS search L P VS L P VS max sum (sec) (sec) (sec) (sec) (sec) (sec) (sec) Coffee 47 1019 30 4379 2651 151 154 widget 397 10142 109 89605 48695 707 703 Pavement 250 345 35 841 126 97 96 Table 5.4: Search running time 5.2.1 Search running time The first experiment compares the time required to search for good projection schemes by minimizing different error bounds. Table 5.4 shows the timing of all search algorithms proposed in Chapters 3 and 4 to find a good projection for each a-vector in all the optimal value functions of the first 15 stages. Al l search algo-rithms perform a lattice search within the set of projection schemes that partition variables in disjoint subsets. This is because projection schemes with overlapping subsets of variables may or may not be practical depending on whether they allow the construction of a clique tree. The clique tree enables an explicit representation of the belief state which is often necessary for Bayesian inference. Since the focus of this thesis is on approximation quality and due to time constraints, the Bayes net infrastructure for detecting projection schemes that do not allow the construction of a clique tree was not implemented. In principle, there is no technical reason that should prevent such an implementation. Hence, the search is limited to projection schemes with disjoint subsets. Furthermore, assuming that marginals of at most two variables provide a suitable efficiency/accuracy tradeoff, the lattice is traversed until all children of a node correspond to projection schemes with a marginal of more than two variables. This last node is the projection scheme returned by the search. We should point out that in all the experiments to follow, the search algorithms are restricted to projection schemes with marginals of at most two variables (unless otherwise stated). 89 As a reminder, the 5-bound search traverses the lattice greedily by minimiz-ing the worst error induced by a single approximation. Switching can be determined by computing LP-switch tests (Section 3.1.1) or VS-switch tests (Section 4.2). In Table 5.4, as expected, the running time when using VS-switch tests is much less since there are no LPs to be solved. Furthermore, as mentioned above, LP-switch tests are the only algorithms that cannot benefit from the use of compact represen-tations and therefore have a running time dependent on the size of the full state space instead of the effective state space. Note that a [/-bound search is essentially the same as a .B-bound search and therefore the running times are identical. A [/-bound is computed by adding the E-bounds of the current and previous stages. The time required for this sum is a negligible constant when compared to the search itself. As for the .E-bound search, it also traverses the lattice greedily, but by min-imizing the cumulative error induced by consecutive approximations. Hence, in addition to the lattice traversal, it constructs switch sets and Alt-sets. This explains why the running time for an E'-bound search is much longer than for a .B-bound search. Once again, switch tests in the E-bound search can be performed using LPs or the vector space formulation and as expected the latter is significantly faster than the former. Finally, the VS search consists of a greedy traversal of the lattice whereby the relative error rate is minimized. That is, the gradients are made as perpendicular as possible to the subspace of displacement vectors D. Since there are several gradients to take into consideration, we can minimize (among other things) the sum of all relative error rates or their maximum. For either criteria (sum vs max), the running time is roughly the same and it is significantly faster than .B-bound and in-bound search algorithms that use LP-switch tests, but a bit slower if VS-switch tests are used for the .B-bound search. This is because, on one hand, the VS search does not solve any L P (when compared to LP-switch tests), but on the other hand, it has 90 a stronger dependence on the number of a-vectors (when compared to VS-switch tests). A n important observation regarding this experiment is that the time to search for good projections can be much worse than that of solving P O M D P s , which we know is already intractable. In fact, only the search procedures that avoid solving LPs scale well when larger problems need to be tackled. The VS procedures have a running time that is roughly of the same order of magnitude as the solution procedures. 5 . 2 . 2 E r r o r b o u n d e v a l u a t i o n In the second experiment, the B, U and E bounds are compared to the average error incurred in 5000 random policy executions. Tables 5.5, 5.6 and 5.7 show the results of the experiment for each test problem. In each table there is one column per search algorithm and one row per error bound (or error average). Al l entries in a table are interpreted as an error bound or an error average (indicated by the row label) for a given search algorithm (indicated by the column label). The first two rows evaluate the error due to a single approximation at 15 stages to go. The average error is the average loss incurred for 5000 random initial belief states generated from a uniform distribution. Note that the same 5000 samples were used to evaluate all search algorithms in all tables. The last three rows evaluate the cumulative error due to several approximations during the execution of a 15-stage policy. The average error denotes the average cumulative loss for those same 5000 uniformly random initial belief states. Looking at the tables, it is striking how large the B, U and E bounds are compared to the average error observed. This is explained in part by the fact that the bounds are concerned with the worst case scenario whereas the errors obtained through sampling are averaged out. The second reason is that the bounds are not tight. As mentioned in Section 3.1, the switch sets computed when dealing with 91 Error 5-bound search E-bound search VS search L P VS L P VS max sum Single Average 0.001301 0.006278 0.006278 0.006278 0.001336 0.001349 Approx. .B-bound 3.284000 5.915000 4.391000 5.915000 3.284000 3.284000 Several Average 0.014351 0.016113 0.016113 0.016113 0.015433 0.010733 Approx. [/-bound 24.85 42.47 32.60 42.47 24.85 24.85 E-bound 13.084810 13.084810 13.084810 13.084810 13.084810 13.084810 Table 5.5: Coffee problem: error bound comparisons at 15 stages to go Error .B-bound search E-bound search VS search L P VS L P VS max sum Single Average 0.035180 0.035193 0.035193 0.035193 0.008152 0.008144 Approx. .B-bound 3.408000 3.627000 3.408000 3.627000 3.408000 3.408000 Several Average 0.050858 0.050818 0.050818 0.050818 0.051912 0.051719 Approx. [/-bound 34.93 37.42 34.95 37.42 34.95 34.93 E'-bound 8.381117 8.381117 8.381117 8.381117 8.381117 8.381117 Table 5.6: Widget problem: error bound comparisons at 15 stages to go Error .B-bound search E-bound search VS search L P VS L P VS max sum Single Average 0.001510 0.001510 0.001510 0.001510 0.001417 0.001415 Approx. B-bound 5.386000 5.690000 5.386000 5.690000 5.368000 5.616000 Several Average 0.006640 0.006640 0.006640 0.006640 0.007101 0.002753 Approx. [/-bound 38.57 40.80 38.87 40.80 38.99 39.52 E-bound 23.217647 35.392262 23.497992 35.392262 23.873747 24.384092 Table 5.7: Pavement problem: error bound comparisons at 15 stages to go 92 projection schemes (nonlinear approximations) are really supersets of the switch set. Switch sets are an integral part of the computation of the B, U and E bounds, meaning that they are all potentially loose. Similarly, when VS-switch tests are used instead of LP-switch tests, a potentially larger superset of the switch set is constructed. Moreover, the U bound is loose by definition, since it simply adds up the B bounds. We introduced the E bound as a tighter alternative to the U bound, however it is also loose as it relies on A/i-sets which are really supersets of the set of all alternative plans. The large difference between bounds and sampled averages suggests two things: • There may not be any point in computing those error bounds, since in practice it is very unlikely to suffer a loss as large as indicated by the bounds. Although the bounds currently appear meaningless, their relative scale may still provide useful information for choosing a good projection. It would also be interesting to see how the bounds compare to the average loss when their looseness is contained. For instance, linear approximation methods allow the computation of exact switch sets, which could significantly improve the bounds' tightness. Finally, as future work, one should consider improving the E bound by con-structing Alt-sets as close as possible to the actual set of alternative plans. • Search algorithms that try to minimize an error bound may not be appropriate in practice. On the other hand, all search algorithms seem to perform equally well since the error bounds and the error averages are all similar. The third experiment (next section) will shed some light regarding this observation. 5.2.3 Search algorithm comparison In the third experiment, we compare the projection schemes found by different search algorithms. Interestingly enough, this comparison reveals that most of the 93 projections found by algorithms that minimize a bound (i.e., .B-bound search with L P or VS-switch tests and E-bound search with L P or VS-switch tests) all yield very similar (if not identical) projections. There is an explanation to this. When traversing the lattice, those algorithms always select the child with the smallest bound (B or E ) . However, when all children have the same bound, those algo-rithms all break ties in the same way, by simply choosing the first child (of some predetermined ordering). It turns out that for most problems, the nodes at the top of the lattice correspond to very fine projection schemes (that preserve few corre-lations) and therefore allowing switching to most if not all a-vectors representing the value function. As defined in Sections 3.1-3.2, the B and E bounds correspond respectively to the single and cumulative error associated with the a-vector in the switch set that contributes the largest such error. Hence, when all the children of a node allow switching to most or all a-vectors, the a-vector with the largest single or cumulative error is likely to be in the switch set of all children, meaning that they all have the same B or E bound. Thus at the beginning of any B or E-bound search, the search is still progressing within the top part of the lattice, yielding roughly the same projections regardless of which bound is minimized. Note that this phenomena is amplified by the fact that supersets of the switch sets are com-puted, and this is even worse when VS-switch tests are used. A possible solution to this problem would be to start the search at some node further down the lattice. For example, one could heuristically pick as a starting node, a projection scheme that would preserve certain correlations that appear important when examining the Bayes net dynamics and the reward functions. As for VS search algorithms, they do not suffer from the above problem. This is because they minimize the maximum relative error rate or the squared sum of all relative error rates. These quantities are very sensitive to the marginals defined by different projection schemes. From a linear algebra point of view, the marginals of each projection scheme defines a subspace D of displacement vectors. The angles 94 between this subspace and each gradient determine the relative error rates. Since those angles change with each projection scheme, ties between children rarely occur and the lattice traversal for each VS search tends to be different. Figures 5.2, 5.3 and 5.4 compare the average cumulative error for the max VS search (minimize maximum relative error rate), the sum VS search (minimize sum of squared relative error rates) and the .B-bound search with LP-switch tests. The other S-bound and i?-bound search algorithms were not included in the comparisons as they yield very similar or identical projection schemes than the -B-bound search with LP-switch tests. The graphs indicate the average cumulative loss in terms of the number of stages to go for the same 5000 policy executions (starting in different initial belief states chosen uniformly randomly) that were used in the experiment of the previous section. In theory, error bars cannot be negative, however, because the initial belief states were sampled randomly, it may happen that the average discounted cumulative reward is higher than the optimal expected total reward. Furthermore, error bars do not necessarily increase monotonically with the number of stages to go in general. When a switch occurs, it usually is to a plan of lower expected total reward. However, if the current plan is not optimal (due to previous approximations), a switch may be beneficial as it may be to a plan of higher expected total reward, essentially diminishing the error caused by previous approximations. On the other hand, as shown by the graphs, the average cumulative error tends to increase with the number of stages to go. Since P O M D P s are assumed to have finite reward functions, this error eventually stops growing. More experiments would be required to show when the error levels off in practice. In Figure 5.4, the graph for the pavement problem indicates a sudden large cumulative error at 7 stages to go for the S-bound search and at 8 stages to go for the max VS search. After those stages, the error diminishes for a few stages and starts growing again. This intriguing behavior is easily explained by Figure 5.5 which shows the error due to a single approximation at each stage. It turns out 95 x 10"3 B-bound search (with LP-switch tests) I- I Max VS search I I Sum VS search _51 i I I I I I I I I I I I I I I I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Stages to go Figure 5.2: Coffee problem: comparison of the average cumulative error obtained by different search algorithms that a large error is incurred at 7 and 8 stages to go for the B-bound search and the max VS search algorithms, which explains the sudden jump in cumulative error at those stages in Figure 5.4. Then, for a few stages, approximations do not yield any error, so the cumulative error naturally decreases due to the discount factor. It starts growing again at 13 stages to go when some errors start appearing. For the coffee and pavement problems, the cumulative error bars correspond-ing to the sum VS search are lower than those corresponding to the max VS search and the B-bound search, whereas for the widget problem, the B-bound search algo-rithm provides the smallest cumulative errors. From those graphs it is not possible to decide which search method is likely to perform better than the others in general. 96 0.06 0.05 0.04 0.03 0.02 0.01 -0.01 n 1 1 1 1 1 r B-bound search (with LP-switch tests) W Max VS search I I Sum VS search _ • • rni—I E C _l I I 1_ • l I.. I _l I I I I l_ 1 2 3 4 5 7 8 9 10 11 12 13 14 15 Stages to go Figure 5.3: Widget problem: comparison of the average cumulat ive error obtained by different search algorithms 97 12 10 x 10 ' > 6 -2 1^ 1 B-bound search (with LP-switch tests) la^ l Max VS search I I Sum VS search Oh 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Stages to go Figure 5.4: Pavement problem: comparison of the average cumulat ive error obtained by different search algorithms 98 0.012 0.01 h 0.008 S 0.006 0.004 0.002 h • • B-bound search (with LP-switch tests) [iPl Max VS search I I Sum VS search _i i i i_ j i , i i i_ 1 2 3 4 5 7 8 9 10 11 12 13 14 15 Stages to go Figure 5.5: Pavement problem: comparison of the average error due to a singl approximat ion at each stage for different search algorithms 99 Furthermore, the results of the experiment may be biased by the choice of a uniform prior when picking the 5000 initial random belief states. The prior definitely influ-ences the frequency with which some alternative plans are executed and therefore, further experimentation and/or a theoretical analysis would be required to assess the impact of the prior distribution on the performance of each search algorithm. It is also interesting to compare the average number of plan switches that occur during a policy execution when applying the projection schemes found by those three search algorithms (Figures 5.6, 5.7 and 5.8). Although the average cumulative error is the quantity that a decision theoretic agent wants to minimize, the average number of plan switches provides an interesting benchmark since VS search algorithms were designed to minimize the likelihood of switching. As with the average cumulative error, there isn't a search algorithm that clearly leads to fewer switches on average than the others for all three test problems. If we compare the average number of switches for different test problems, it is interesting to note that good approximate belief state monitoring for the widget problem seems to be inherently harder than for the coffee problem which in turn seems to be inherently harder than for the pavement problem. Regardless of which search algorithm is used, the average number of switches is much higher for the widget problem than for the coffee problem, which in turn is also higher than for the pavement problem. This suggests a correlation with the average number of a-vectors necessary to represent the value functions. In fact, as indicated in Table 5.4, the widget problem has the highest average number of a-vectors per value-function followed by the coffee problem and finally the pavement problem. Once again, further investigation is needed to assess the potential correlation between the number of a-vectors and the likelihood of switching. In a last comparison, we look at the progress (in terms of reducing the average cumulative error) achieved while traversing the lattice downwards. In Section 3.3, we showed that any descendant of a node has a corresponding projection scheme 100 1.4 <n 1.2 J3 E 0.8 E o 0.6 0.4 0.2 • • B-bound search (with LP-switch tests) I I Max VS search I I Sum VS search III •mn MCI i n i l l I 7 8 9 Stages to go 11 12 13 14 15 Figure 5.6: Coffee problem: comparison of the average cumulative number switches for different search algorithms 101 B-bound search (with LP-switch tests) Haral Max VS search 1 I Sum VS search Stages to go Figure 5.7: Widget problem: comparison of the average cumulative number of switches for different search algorithms 102 0.35 0.3 £ 0.25 •o 0.2 CO | 0.15 § 0.1 < 0.05 B-bound search (with LP-switch tests) I I Max VS search I I Sum VS search _i i i i_ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Stages to go Figure 5.8: Pavement problem: comparison of the average cumulat ive number switches for different search algorithms 103 that guarantees (not necessarily strictly) smaller B, U and E bounds. Similarly, in Section 4.3, we showed how the relative error rate decreases monotonically as we go down the lattice. In practice, the real question is: if we allow our favorite algorithm to search deeper in the lattice, does the average cumulative error diminish? Figures 5.9, 5.10 and 5.11 show that the average cumulative error does in fact tend to decrease when the number of stages to go is large. Those three graphs compare the average cumulative error when a search algorithm is restricted to projection schemes with marginals of at most one variable, at most two variables and at most three variables. Results for the B-bound search, max VS search and sum VS search are presented for the coffee problem.2 Note that there is only one projection scheme with marginals of at most one variable and this is when none of the correlations are preserved (i.e., all variables are independent). This naive projection scheme can be considered as a base case since it is at the top of the lattice and there are no simpler projection schemes. Figures 5.9, 5.10 and 5.11 confirm that it is usually possible to do much better than the naive base case. 2 The widget and pavement problems yield similar results. 104 0.035 0.03 0.025 I 002 0.015 0.01 0.005 -0.005 At most 1 variable per marginal PIS] at most 2 variables per marginal I I At most 3 variables per marginal l l D 7 8 9 Stages to go 10 11 12 13 14 15 Figure 5.9: B - b o u n d search w i t h L P - s w i t c h tests for the coffee problem: comparison of the average cumulative error when the search is restricted to projection schemes w i t h marginals of at most 1, 2, or 3 variables. 105 0.035 0.03 0.025 I OO2 0.015 0.01 0.005 -0.005 • • At most 1 variable per marginal IBW at most 2 variables per marginal I I At most 3 variables per marginal IID __D - J II 7 8 9 Stages to go 10 11 12 13 14 15 Figure 5.10: Max VS search for the coffee problem: comparison of the average cumulative error when the search is restricted to projection schemes with marginals of at most 1, 2, or 3 variables. 106 0.035 0.03 0.025 0.02 0.015 0.01 0.005 -0.005 • • At most 1 variable per marginal at most 2 variables per marginal I I At most 3 variables per marginal iiD J ID:, ID BJ 7 8 9 Stages to go 10 11 12 13 14 15 Figure 5.11: Sum VS search for the coffee problem: comparison of the average cumulative error when the search is restricted to projection schemes with marginals of at most 1, 2, or 3 variables. 107 Chapter 6 Conclusion 6.1 Summary The primary contribution of this thesis consists of a value-directed framework to perform approximate but efficient belief state monitoring. This framework uses the value function to measure the loss in expected total return incurred when approxi-mating belief states during a policy execution. In Chapter 3, various bounds (B, U and E) on the loss in expected value were derived. The general idea is to construct the set of all plans that may be executed as a result of a single approximation (switch set) or several consecutive approximations (^4/i-set) and to measure the difference in expected total return between the best and the worst plans. These bounds are generic since they can be computed for a wide range of approximation methods in-cluding projection schemes and any linear approximation method (such as density trees). From a practical point of view, the bounds' usefulness is unclear. On one hand, as shown by the experiments in Chapter 5, the average error tends to be significantly smaller than the bounds. This is because the bounds are concerned with the worst case scenario and the algorithms to compute them introduce some looseness. On the other hand, the relative scale of the bounds may provide useful information to choose a good projection. The bounds are then used to direct the search for a good projection scheme 108 by traversing the lattice of projection schemes in a greedy fashion that seeks to minimize some bound. Although in theory the search algorithms guided by those bounds are sound, in practice, several nodes at the top of the lattice exhibit the same error bounds, which provide poor guidance to the search. Furthermore, from a computational point of view, the running time of those search algorithms (B-bound and L7-bound search with LP-switch tests) are worse than that of solving a P O M D P which is already intractable. As a remedy to those various problems, a vector space formulation was introduced in Chapter 4. It enabled us to define VS-switch tests as an alternative to LP-switch tests. The former has the advantage of avoiding the use of LPs which reduces considerably the overall running time of the search algorithms. On the other hand, this speed up is made possible by introducing more looseness in the bounds. The vector space analysis also reveals that each projection defines a sub-space of directions in which the belief state is approximated. Since the difference in expected return between a pair of a-vectors varies more in some directions than others we can try to select good projection schemes that allow approximations in directions of low variance for most pairs of a-vectors. Using the relative error rate as a quantity to minimize during the search (instead of some error bound) leads to the VS search algorithms defined in Chapter 4. These provide alternative search algorithms, which unlike the different L?-bound and i?-bound search algorithms, do not suffer from guidance problem since the relative error rate is usually different for each node (even near the top of the lattice). Furthermore, the running time of VS procedures scales better when tackling large P O M D P s as it is roughly the same order of magnitude as the solution procedure. 6.2 Fu tu re Framework Enhancements A brief experimental evaluation of the framework was carried out in Chapter 5. A l -though limited in scope due to the lack of efficient solution algorithms for POMDPs , 109 the experiments enabled us to show how the different algorithms behave in prac-tice on a few test problems. The framework came out of a theoretical study of the approximate belief state monitoring problem and therefore it suffers from several practical deficiencies. A number of directions may be taken to improve the prac-ticality of the bounds and the algorithms. For instance, the primary drawback of the bounds is their looseness. Further research to develop algorithms that compute tighter switch sets and A/i-sets is necessary. Also, the bounds are concerned with the worst case scenario, so it would be nice to know under what circumstances this worst case scenario, or some other really bad scenarios, are likely to occur and with what frequency. In the end, since an agent seeks to maximize the expectation of its total return, what really matters is not so much the worst case, but rather the average case. Therefore, it would be desirable to have a better understanding of how approximate belief state monitoring influences the agent's returns on average. The experiments carried out were concerned with finite-horizon P O M D P s only. Although the author believes that most of the results obtained for finite-horizon problems translate into very similar results for infinite-horizon problems, further experimentation remains to be done. A n important question arises for infinite-horizon problems: we know that the cumulative error tends to increase with the number of stages to go and that it remains bounded (since rewards are assumed to be finite), so in the long run, what does the average cumulative error converge to? Most importantly, how far is it from optimal? This is a key issue for which theoretical as well as practical insights would be desirable. As for the search algorithms, they suffer from the same sources of intractabil-ity as the algorithms to solve POMDPs. In this work, we used factored represen-tations as much as possible to counter one source of intractability, namely, the size of the state space. However, not all POMDPs allow a small enough factored rep-resentation and another source of intractability remains: the exponentially growing number of a-vectors. Hence, the proposed algorithms are intractable in the same 110 way that solution algorithms are. Further research is necessary to develop more ad-vanced techniques that can mitigate those sources of intractability for some classes of POMDPs. It is interesting to note that in the event where such techniques would be developed, then the solution algorithms as well as the search algorithms should become tractable for the same classes of POMDPs. Currently, the framework provides an analysis for approximation methods such as projection schemes, density trees and any other linear approximation method. It would be nice to extend it to sampling methods as they are simple to use, very effi-cient and they do not assume discrete state variables. In the literature, approximate belief state monitoring methods that use some form of sampling include particle fil-tering [12, 11], Monte Carlo algorithms [24], condensation algorithms [20], survival of the fittest [23], etc. As with the other approximation methods, those sampling schemes have been applied to monitor general dynamical systems free of any deci-sion process. Value-directed versions of those sampling methods would essentially concentrate the sampling efforts to sensitive areas of the belief space for which the optimal plan to execute is less certain. Sampling methods can also be combined with projection schemes for a further speed up as proposed by Doucet, Freitas, Murphy and Russell [8]. This method, called Rao-Blackwellised particle filtering, should also be analyzed from a value-directed point of view. Finally, an interesting extension would be to integrate this value-directed framework to the algorithms that solve POMDPs. In other words, as P O M D P s are being solved, the solution algorithms could take into account the fact that belief states will be approximated. Ultimately, a decision theoretic agent would seek a bounded-optimal solution to its P O M D P since it would try to compute a policy with the highest expected total return given some bound on the amount of time it has to monitor its belief state during policy execution. I l l Appendix A Basics of Vector Spaces In what follows, we present a brief overview of some relevant notions of linear algebra for the development of Chapter 4. For a more thorough overview, the reader is referred to any introductory textbook of linear algebra. Definition 3 A vector space is roughly speaking a set V of vectors, with two operations (vector addition and scalar multiplication) such that: • For all vectors v\, v2 € V,v\ + V2 6 V • For any scalar c and for any vector v € V, cv £ V For our purposes, the set of all |S|-dimensional (real) vectors is a vector space which contains all a-vectors as well as all belief states. Definition 4 Let V be a vector space, then a subspace of V is a subset W which is itself a vector space. Geometrically, a subspace can be viewed as a set of vectors that are uncon-strained in length, but constrained in direction. For instance, let V be the vector space corresponding to K 3 . The x-axis is a one dimensional subspace of V that con-tains all vectors of the form (a;, 0,0). Since all those vectors are parallel (they are on the s-axis), then they have the same direction (assuming we ignore orientation). 112 The yz-plane is another subspace which contains all vectors of the form (0,y,z). Those vectors can have several directions but they are restricted to the yz-plane. Definition 5 Let W be a subspace of V, then we define the null space of W as the largest subspace W1- of V such that for all w £ W, w' £ W^, the dot product of w and w' is zero (w • w' = 0). It is interesting to note that the dot product of two vectors is zero if and only if they are perpendicular. More generally, recall that the dot product of two vectors v and w is proportional to the cosine of the angle 9VW between them: v • w = IMI2IMI2 cos0vw Hence, when two vectors are perpendicular, their dot product is zero. Since the vectors of a subspace and its null space are pairwise perpendicular, we can say that a susbpace and its null space are perpendicular subspaces. For example, the x-axis subspace is the null space of the yz-plane subspace in 5R3 and they are clearly perpendicular. Definition 6 Let V be a vector space, then a set of vectors W is a spanning set of V if every v £ V is a linear combination of the vectors in W. That is, v — J2wtew c i w i > where IOJ £ W and Ci is some scalar. Definition 7 The vectors of some set W are linearly independent if and only if Yjwiew ciwi = 0 is satisfied only when ci — 0 for all i. Definition 8 Let V be a vector space, then a basis B is a smallest spanning set of V composed of linearly independent vectors. Definition 9 The dimensionality of a subspace V is given by the smallest number of linearly independent vectors necessary to span it. Thus the number of dimensions of a subspace V corresponds to the size of a basis for V. 113 D e f i n i t i o n 10 Let V be a vector space, then an orthonormal basis B is a basis of V such that: • Vu G B, v is normal: \\v\\2 = 1. • Vvi,V2 G B, v\ and v2 are orthogonal: v\ • v2 — 0. Any basis can be transformed into an orthonormal basis by applying the Gram-Schmidt orthogonalization process. Orthonormal bases are useful when com-puting the linear projection of a vector on some subspace. D e f i n i t i o n 11 The linear projection of a vector v on some other vector w is roughly speaking the component of v that is parallel to (has the same direction as) w. Formally, the projection proj(v,w) of v on w is: In turn, the linear projection of a vector v on some vector space V is roughly speaking the greatest component of v that is parallel to (has the same direction as) some vector v' G V. If V has an orthonormal basis B, then one can compute the projection proj(v, V) of v on V as follows: projiy, w) — v • w w w\\2 •w{eB wieB 114 Appendix B Test Problems The full specifications for the coffee delivery problem, the widget production problem and the pavement maintenance problem follow. The notation used to specify each P O M D P is similar to the notation used by Hoey and St.Aubin on their SPUDD (Stochastic Planning using Decision Diagrams) website (http://www.cs.ubc.ca/ spider/jhoey/spudd/submit.html) to describe MDPs using ADDs. Each P O M D P specification includes: • Set of state variables. • Set of actions. • Set of observations. • Transition function for each action. A transition function is described by a set of conditional probability tables (CPTs) indicating the probabilistic depen-dencies of each state variable (at the current time step) on the state variables at the current and previous time step. Each C P T is represented compactly by a decision tree. • Observation function for each action. A n observation function describes the probabilistic depencies of each observation on the current state variables. As for transition functions, the dependencies are represented using decision trees. 115 • Reward function. For each action, a decision tree describes the immediate reward earned in terms of the value of the current state variables. • Discount factor (number between 0 and 1). B . l Coffee Delivery The coffee delivery problem is a variation on the problem introduced by Boutilier and Poole [2]. Roughly speaking, a robot must deliver coffee to a user when the user wants coffee (variable wc is true), but doesn't have any coffee (variable he is false). The robot has two actions: getC (to get coffee) and testC (to verify if the user wants coffee). When the robot gets coffee, it must go across the street to the local coffee shop to buy coffee. When doing this, it may get wet (variable w is true) if it is raining (variable r is true) and the robot doesn't have any unmbrella (variable u is false). Generally speaking, the robot earns rewards when the user wants coffee (wc is true) and has coffee (he is true), and it is penalized otherwise. The robot is further penalized if it gets wet. A small cost is incurred each time it gets coffee, since going across the street consumes a significant amount of energy. variables (w r he u wc) actions (getC testC) observations (ob_wc ob_nwc) action getC r (r ( 1 . 0 ) ( 0 . 0 ) ) u (u ( 1 . 0 ) ( 0 . 0 ) ) w (r (u (w ( 1 . 0 ) ( 0 . 0 ) ) (w ( 1 . 0 ) ( 1 . 0 ) ) ) 116 (u (w ( 1 . 0 ) ( 0 . 0 ) ) (w ( 1 . 0 ) ( 0 . 0 ) ) ) ) he (he ( 1 . 0 ) ( 0 . 9 ) ) wc (wc ( 0 . 1 ) ( 0 . 0 ) ) e n d a c t i o n a c t i o n t e s t C r ( r ( 1 . 0 ) ( 0 . 0 ) ) u (u ( 1 . 0 ) ( 0 . 0 ) ) w (w ( 1 . 0 ) ( 0 . 0 ) ) he (he ( 0 . 7 ) ( 0 . 0 ) ) wc (wc ( 1 . 0 ) ( 0 . 3 ) ) e n d a c t i o n o b s e r v a t i o n ge tC ob_wc ( 1 . 0 ) ob_nwc ( 0 . 0 ) e n d o b s e r v a t i o n o b s e r v a t i o n t e s t C ob-wc (wc ( 0 . 8 ) ( 0 . 1 ) ) ob j iwc (wc ( 0 . 2 ) ( 0 . 9 ) ) e n d o b s e r v a t i o n r e w a r d ge tC (w (he (wc ( 0 . 0 ) ( - 2 . 0 ) ) (wc ( - 4 . 0 ) ( - 2 . 0 ) ) ) (he (wc ( 1 . 0 ) ( - 1 . 0 ) ) 117 (wc (-3.0) (-1.0)))) t e s t e (w (he (wc (0.5) (-1.5)) (wc (-3.5) (-1.5))) (he (wc (1.5) (-0.5)) (wc (-2.5) (-0.5)))) endreward discount 0.90 B.2 Widget Production The following problem is a variation on the widget problem introduced by Draper, Hanks and Weld [10]. A manufacturing robot is in charge of processing widgets. A widget can be flawed (fl), slightly flawed (slfl), painted (pa), shipped (sh) or rejected (re). Using the inspect action, the robot can detect (more or less) whether or not a widget is flawed or slightly flawed. When a widget is not flawed nor slightly flawed, the goal of the robot is to paint it and then to ship it. If it is slightly flawed, it should first repair it, then paint it and ship it. Finally, if it is flawed, it should simply reject it. When the robot is done processing a widget it notifies the supervisor and starts processing a new random widget. As it notifies the supervisor, it also gets a reward if a painted widget without any flaw was shipped or a flawed widget was rejected. Otherwise, it is penalized for processing the widget improperly. variables ( f l s l f l pa sh re) actions (inspect repair paint ship reject notify) observations (bad slbad ok) 118 action inspect f l ( f l (1.0) (0.0)) s l f l ( s l f l (1.0) (0.0)) pa (pa (1.0) (0.0)) sh (sh (1.0) (0.0)) re (re (1.0) (0.0)) endaction action repair f l ( f l (1.0) (0.0)) s l f l ( s l f l ( f l (1.0) (sh (1.0) (re (1.0) (0.05)))) (0.0)) pa (pa (1.0) (0.0)) sh (sh (1.0) (0.0)) re (re (1.0) (0.0)) endaction action paint f l ( f l (1.0) (0.0)) s l f l ( s l f l (1.0) (0.0)) pa (pa (1.0) (sh (0.0) (re (0.0) (0.95)))) sh (sh (1.0) (0.0)) 119 re (re (1.0) (0.0)) endaction action ship f l ( f l (1.0) (0.0)) s l f l ( s l f l (1.0) (0.0)) pa (pa (1.0) (0.0)) sh (re (0.0) (1.0)) re (re (1.0) (0.0)) endaction action reject f l ( f l (1.0) (0.0)) s l f l ( s l f l (1.0) (0.0)) pa (pa (1.0) (0.0)) sh (sh (1.0) (0.0)) re (sh (0.0) (1.0)) endaction action notify f l (0.3) s l f l (0.3) pa (0.0) sh (0.0) re (0.0) endaction observation inspect bad ( f l ( 1 . 0 ) ( 0 . 0 5 ) ) s l b a d ( f l ( 0 . 0 ) ( s l f l ( 0 .95 ) ( 0 . 0 ) ) ) ok ( f l ( 0 . 0 ) ( s l f l ( 0 . 0 ) ( 0 . 9 5 ) ) ) e n d o b s e r v a t i o n o b s e r v a t i o n r e p a i r bad ( 0 . 0 ) s l b a d ( 0 . 0 ) ok ( 1 . 0 ) e n d o b s e r v a t i o n o b s e r v a t i o n p a i n t bad ( 0 . 0 ) s l b a d ( 0 . 0 ) ok ( 1 . 0 ) e n d o b s e r v a t i o n o b s e r v a t i o n s h i p bad ( 0 . 0 ) s l b a d ( 0 . 0 ) ok ( 1 . 0 ) e n d o b s e r v a t i o n o b s e r v a t i o n r e j e c t bad ( 0 . 0 ) s l b a d ( 0 . 0 ) 121 ok (1.0) endobservation observation not i fy bad (0.0) slbad (0.0) ok (1.0) endobservation reward inspect (-0.2) repair (-0.45) paint (-0.45) ship (0.0) reject (0.0) not i fy (sh ( f l (re endreward discount 0.95 B.3 Pavement Maintenance This problem is inspired from the pavement maintenance problem described by Pu te rman [32]. The idea is to find an opt imal maintenance schedule to minimize the cost of road maintenance. Every year, the local government must decide i f it 122 (-2.0) ( s l f l (-1.0) (pa (1.0) (-0.5)))) ( f l (1.0) (-1.0)) (-0.5))) should redo the pavement, patch it, inspect it, or simply do nothing. This decision is based on an estimate of 7 binary attributes of the pavement (state variables a, b, c, d, e, / , g). Brand new pavement with no imperfections has all 7 attributes set to true. Over the years, the pavement gradually deteriorates and consequently the variables representing those attributes stochastically tend to become false. There are two classes of attributes, the surface attributes (variables a, b, e, /) and the internal attributes (variables c, <i, g). The patch action fixes only the surface attributes whereas the redo action fixes all attributes. Each action has an inherent cost that varies with the amount of work required. A n additional cost measuring voters' dissatisfaction with respect to the general state of the roads is also incurred. The goal of the goverment is to minimize the combination of those costs as indicated by the negative reward function below. v a r i a b l e s (a b c d e f g) a c t i o n s ( p a t c h redo i n s p e c t n o t h i n g ) o b s e r v a t i o n s (good ok bad) a c t i o n n o t h i n g a (a ( 0 . 9 ) ( 0 . 0 ) ) b (b ( 0 . 8 ) ( 0 . 0 ) ) c (c (a ( 0 . 9 ) ( 0 . 6 ) ) ( 0 . 0 ) ) d (d (b ( 1 . 0 ) ( 0 . 8 ) ) ( 0 . 0 ) ) e (e ( 0 . 9 ) ( 0 . 0 ) ) f ( f ( 0 . 8 ) ( 0 . 0 ) ) g (g ( f (e ( 1 . 0 ) ( 0 . 9 ) ) 123 ( 0 . 8 ) ) . ( 0 . 0 ) ) e n d a c t i o n a c t i o n i n s p e c t a (a (0 9) (0 0 ) ) b (b (0 8) (0 0 ) ) c (c (a ( 0 . 9 ) ( 0 . 6 ) ) (0 0 ) ) d (d (b ( 1 . 0 ) ( 0 . 8 ) ) (0 0 ) ) e (e (0 9) (0 0 ) ) f ( f (0 8) (0 0 ) ) g (g ( f (e (1 0) (0 . ( 0 . 8 ) ) ( 0 . 0 ) ) e n d a c t i o n a c t i o n p a t c h a ( 0 . 9 ) b ( 0 . 9 5 ) c (c (a ( 0 . 9 ) ( 0 . 0 ) ) d (d (b ( 1 . 0 ) ( 0 . 0 ) ) e (0 .85 ) f ( 0 . 9 5 ) g (g ( f (e (1 ( 0 . 6 ) ) ( 0 . 8 ) ) .0) ( 0 . 9 ) ) ( 0 . 8 ) ) ( 0 . 0 ) ) e n d a c t i o n a c t i o n r edo a ( 1 . 0 ) b ( 1 . 0 ) c ( 0 . 9 5 ) d ( 0 . 9 ) e ( 1 . 0 ) f ( 1 . 0 ) g (0 .95 ) e n d a c t i o n o b s e r v a t i o n n o t h i n g good ( 1 . 0 ) ok ( 0 . 0 ) bad ( 0 . 0 ) e n d o b s e r v a t i o n o b s e r v a t i o n i n s p e c t good ( f (a (b ( 0 . 9 ) ( 0 . 7 ) ) ( 0 . 8 ) ) (b ( 0 . 7 ) ( 0 . 1 ) ) ) ok ( f ( a (b ( 0 . 1 ) ( 0 . 3 ) ) ( 0 . 2 ) ) ( 0 . 0 ) ) bad ( f ( 0 . 0 ) (b ( 0 . 3 ) ( 0 . 9 ) ) ) e n d o b s e r v a t i o n o b s e r v a t i o n p a t c h good (g (d (c ( 0 . 7 ) ( 0 . 6 ) ) ( 0 . 4 ) ) ( 0 . 3 ) ) ok (g ( 0 . 2 ) ( 0 . 6 ) ) bad (g (d (c ( 0 . 1 ) ( 0 . 2 ) ) ( 0 . 4 ) ) ( 0 . 1 ) ) e n d o b s e r v a t i o n o b s e r v a t i o n redo ok ( 1 . 0 ) c r ( 0 . 0 ) ho ( 0 . 0 ) e n d o b s e r v a t i o n r e w a r d i n s p e c t (c (d (g ( - 0 . 5 ) ( - 1 . 5 ) ) ( - 2 . 5 ) ) (g ( - 2 . 5 ) ( - 3 . 5 ) ) ) n o t h i n g (c (d (g ( 0 . 0 ) ( - 1 . 0 ) ) ( - 2 . 0 ) ) (g ( - 2 . 0 ) ( - 3 . 0 ) ) ) p a t c h (c (d (g ( - 1 . 0 ) ( - 2 . 0 ) ) ( - 3 . 0 ) ) 126 (g ( - 3 . 0 ) ( - 4 . 0 ) ) ) r edo (c (d (g ( - 6 . 0 ) ( - 7 . 0 ) ) ( - 8 . 0 ) ) (g ( - 8 . 0 ) ( - 9 . 0 ) ) ) endreward d i s c o u n t 0 .90 Bibl iography [1] K. J. Astrom. Optimal control of Markov decision processes with incomplete state estimation. J. Math. Anal. Appl, 10:174-205, 1965. [2] Craig Boutilier and David Poole. Computing optimal policies for partially observable decision processes using compact representations. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 1168-1175, Portland, OR, 1996. [3] Xavier Boyen and Daphne Roller. Tractable inference for complex stochas-tic processes. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, pages 33-42, Madison, W l , 1998. [4] Anthony R. Cassandra, Leslie Pack Kaelbling, and Michael L . Littman. Act-ing optimally in partially observable stochastic domains. In Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 1023-1028, Seat-tle, 1994. [5] Anthony R. Cassandra, Michael L. Littman, and Nevin L . Zhang. Incremental pruning: A simple, fast, exact method for POMDPs . In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, pages 54-61, Providence, RI, 1997. [6] Hsien-Te Cheng. Algorithms for Partially Observable Markov Decision Pro-cesses. PhD thesis, University of British Columbia, Vancouver, 1988. 128 [7] Thomas Dean and Keiji Kanazawa. A model for reasoning about persistence and causation. Computational Intelligence, 5(3):142—150, 1989. [8] Arnaud Doucet, Nando de Freitas, Kevin Murphy, and Stuart Russell. Rao-Blackwellised particle filtering for dynamic Bayesian networks. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, pages 176-183, Stanford, 2000. [9] A. Drake. Observation of a Markov process through a noisy channel. PhD thesis, Massachusetts Institute of Technology, 1962. [10] Denise Draper, Steve Hanks, and Daniel Weld. Probabilistic planning with information gathering and contingent execution. In Proceedings of the Second International Conference on AI Planning Systems, pages 31-36, Chicago, 1994. [11] J. E . Handschin. Monte Carlo techniques for prediction and filtering of non-linear stochastic processes. Automatica, 6:555-563, 1970. [12] J. E . Handschin and D. Q. Mayne. Monte Carlo techniques to estimate the con-ditional expectation in multi-stage non-linear filtering. International Journal of Control, 9(5):547-559, 1969. [13] Eric A. Hansen. An improved policy iteration algorithm for partially observ-able MDPs. In Proceedings of Conference on Neural Information Processing Systems, pages 1015-1021, Denver, C O , 1997. [14] Eric A. Hansen. Solving POMDPs by searching in policy space. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, pages 211-219, Madison, Wisconsin, 1998. [15] Eric A. Hansen and Zhengzhu Feng. Dynamic programming for P O M D P s using a factored state representation. In Proceedings of the Fifth International Conference on AI Planning Systems, Breckenridge, C O , 2000. 130-139. 129 [16] Eric J. Hansen. Finite-memory control of partially observable systems. PhD thesis, University of Massachusetts Amherst, Amherst, 1998. [17] Milos Hauskrecht. Value-function approximations for partially observable Markov decision processes. Journal of Artificial Intelligence Research, 13:33-94, 2000. [18] Jesse Hoey, Robert St-Aubin, Alan Hu, and Craig Boutilier. SPUDD: Stochas-tic planning using decision diagrams. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 279-288, Stockholm, 1999. [19] Cecil Huang and Adnan Darwiche. Inference in belief networks: A procedural guide. Approximate Reasoning, 11:1-158, 1994. [20] Michael Isard and Andrew Blake. CONDENSATION—conditional density propagation for visual tracking. International Journal of Computer Vision, 29(1):5-18, 1998. [21] Michael I. Jordan, Zoubin Ghahramani, Tommi S.Jaakkola, and Lawrence K. Saul:ml99. A n introduction to variational methods for graphical models. Ma-chine Learning, 37:183-233, 1999. [22] Leslie Pack Kaelbling, Michael Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101:99-134, 1998. [23] Keiji Kanazawa, Daphne Roller, and Stuart Russell. Stochastic simulation algorithms for dynamic probabilistic networks. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, pages 346-351, Montreal, 1995. [24] G. Ritagawa. Monte Carlo filter and smoother for non-gaussian nonlinear state space models. Journal of Computational and Graphical Statistics, 5:1-25, 1996. 130 [25] Uffe Kjaerulff. A computational scheme for reasoning in dynamic probabilistic networks. In Proceedings of the Eighth Conference on Uncertainty in Artificial Intelligence, pages 121-129, Stanford, 1992. [26] Daphne Koller and Raya Fratkina. Using learning for approximation in stochas-tic processes. In Proceedings of the 15th International Conference on Machine Learning, pages 287-295, Madison, 1998. [27] Michael L . Littman, Anthony R. Cassandra, and Leslie Pack Kaelbling. Ef-ficient dynamic-programming updates in partially observable Markov decision processes. Technical Report CS-95-19, Brown University, 1995. [28] Michael L . Littman, Judy Goldsmith, and Martin Mundhenk. The computa-tional complexity of probabilistic planning. Journal of Artificial Intelligence Research, 9:1-36, 1998. [29] William S. Lovejoy. A survey of algorithmic methods for partially observed Markov decision processes. Annals of Operations Research, 28:47-66, 1991. [30] Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of proba-bilistic planning and infinite-horizon partially observable Markov decision prob-lems. In Proceedings of the Sixteenth National Conference on Artificial Intelli-gence, pages 541-548, Orlando, 1999. [31] George E . Monahan. A survey of partially observable Markov decision pro-cesses: Theory, models and algorithms. Management Science, 28:1-16, 1982. [32] M . L . Puterman. Markov decision problems. Wiley, New York, 1994. [33] Y . Sawagari and T. Yoshikawa. Discrete-time Markovian decision processes with incomplete state observation. Annals of Mathematical Statistics, 41:78-86, 1970. 131 [34] Richard D. Smallwood and Edward J. Sondik. The optimal control of par-tially observable Markov processes over a finite horizon. Operations Research, 21:1071-1088, 1973. [35] Edward J. Sondik. The optimal control of partially observable Markov Decision Processes. PhD thesis, Stanford university, Palo Alto, 1971. [36] Edward J. Sondik. The optimal control of partially observable Markov processes over the infinite horizon: Discounted costs. Operations Research, 26:282-304, 1978. [37] Sebastian Thrun. Monte Carlo POMDPs. In Proceedings of Conference on Neural Information Processing Systems, pages 1064-1070, Denver, 1999. [38] Nevin L. Zhang and Wenju Liu. Planning in stochastic domains: Problem characteristics and approximation. Technical Report HKUST-CS96-31, Hong Kong University of Science and Technology, 1996. 132
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Graduate
Approximate value-directed belief state monitoring for partially observable Markov decision processes
Text