Reinforcement Learning in POMDPs Without Resets

1 Introduction

We address the problem of lifelong learning in a partially observable Markov decision process (a POMDP). We consider the most general setting where an agent begins in an unknown POMDP and desires to obtain near optimal reward. In this setting, the agent is forced to obey the dynamics of the environment, which, in general, do not permit resets.

The problem of lifelong learning has been well studied for observable MDPs. Kearns and Singh (1998) provide the E3 algorithm, which has finite (polynomial) time guarantees until the agent obtains near optimal reward. Unfortunately, such an algorithm is not applicable in the more challenging POMDP setting. In fact, none of the guarantees in the literature for learning in the limit for MDPs apply to POMDPs, for reasons which are essentially due to the partially observability.

For POMDPs, the problem of balancing exploitation with exploration has received rather little attention in the literature - typically most results in POMDPs are on planning (see for example Sondik (1971); Lovejoy (1991a, 1991b); Hauskrecht (1997); Cassandra (1998)). Most of the existing learning algorithms such as Parr and Russell (1995); Peshkin et al. (2000) either assume a goal state or assume a reset button. In fact, to the best of our knowledge, the literature does not

Yishay Mansour

School Computer Science Tel-Aviv University Tel-Aviv, Israel 69978 mansour@post.tau.ac.il

contain even asymptotic results for general POMDPs which guarantee that the average reward of an agent will be near optimal in the limit.

Part of the technical difficulty is that there are currently no general results for belief state tracking with an approximate model showing that divergence in the belief state does not eventually occur. Crudely, the issue is that if a belief state is being tracked in an approximate manner, then it is important to show that this approximation quality does not continually degrade with time - otherwise the agent will eventually loose track of the belief state in the infinite horizon (this of course is not an issue in an MDP where the current state is observable). Boyen and Koller (1998) address the issue of approximate belief state tracking, but in their setting the model is known perfectly and their goal is to keep a compact representation of the belief state. Note that approximate belief state tracking is much simpler if the agent is only acting over a fixed finite horizon, since then one can bound the error accumulation as a function of the horizon.

We present new algorithms for learning in POMDPs which guarantee that the agent will obtain the optimal average reward in the limit. Furthermore, we provide a finite time convergence rates for one of our algorithms which has an exponential dependence on a certain horizon time (of an optimal strategy) but has no dependence on the number of states in the POMDP. This result is reminiscent of the trajectory tree algorithm of Kearns et al. (1999) which has similar dependencies (though there they assumed access to a generative model, which allowed simulation of the POMDP). Given the plethora of complexity results in the literature on planning in POMDPs (see Lusena et al. (2001)), we feel these dependencies are the best one could hope for in the most general setting.

Central to our algorithms is the implementation of an approximate reset strategy or a homing strategy. The idea of a reset strategy is not new to the literature - homing sequences were used in the learning of deterministic finite automata (see Rivest and Schapire (1993), though there the sequence provided exact resets). Here, the agent follows a homing strategy in order to move approximately towards a reset. We show that such a strategy always exists, and our finite convergence rates also depend on a characteristic time it takes to approximately reset. However, note that existence of such a strategy alone does not imply that such a strategy will be useful.

The reason is that the agent must take actions to reset, which might otherwise be better spent exploring or exploiting. It turns out that our algorithms use the homing strategy while both exploring and exploiting. In fact, they use the homing strategies infinitely often, which, unfortunately, detracts from exploiting. However, we are able to show that the ratio of the time these homing strategies are used compared to the time spent exploiting is decreasing sufficiently rapidly, such that near optimal average reward can be obtained.

2 Preliminaries

A Partially Observable Markov Decision Process (POMDP) is defined by a finite set of states S, an initial state s0, a set of actions A, a set of observations O, with an output model Q, where Q(o, r|s, a) is the probability of observing o and reward r after performing action a at state s (we assume that r ∈ [0, 1]), and a set of transitions probabilities P, where P(s′ |a, s) is the transition probability from s to s′ after performing action a. We define r(s, a) as the expected reward under Q(·|s, a) after performing action a in state s.

A history h is a sequence of actions, rewards and observations of some finite length, i.e. h = {(a1, r1, o1), ..., (at, rt, ot)}. A strategy or policy in a POMDP is defined as a mapping from histories to actions. We define a belief state B to be a distribution over states. Given an initial belief state B0 let Pr[h|B0] = Pr[r1, o1. . . . , rt, ot|a1, . . . , at,B0] be the probability of observing the sequence of reward-observations (r1, o1, . . . rt, ot) after performing the actions a1 . . . at.

For each strategy π we define its t-horizon expected reward from a belief state B as Rπ t (B) = (1/t)Eh∼π[∑ti=1 r(si, ai)|B0 = B]. A t-Markov strategy is a strategy that depends only on the last t observations. The optimal t-Markov strategy's expected return from initial belief state B is defined as R∗ t (B).

The only assumption we make is that the POMDP is connected, i.e. for all states s, s′ , there exists a strategy π which can reach s′ with positive probability starting from s. (We do not make any ergodicity assumptions, since strategies are by definition non-stationary). Note that if the POMDP is disconnected, then the best statement we could hope for is to obtain the optimal average reward for one of its connected components.

Connectivity implies that there exists a strategy π∗ that maximizes the average reward. More formally, there exists a π∗ such that: i) for every B, limt→∞Rπ∗ t (B) exists and does not depend on B, which we denote by R∗ , and ii) for all π and B, R∗ ≥ limt→∞ supRπ t (B). Hence, for all ϵ > 0 there exist a τ , such that for all B and t ≥ τ :

and we refer to τ as the ϵ-horizon time of the optimal strategy. Essentially, τ is the timescale in which the optimal strategy achieves close to its average reward.

When we say that we restart a t-Markov strategy π from a belief state B we mean specifically that we reset the history, i.e., h = ∅, and run π starting from a state s distributed according to B.

3 Homing Strategies

Clearly, having an action which resets the agent to some designated state would be useful, as it would allow us to test and compare the performance of various policies, starting at the same start state. However, in general, such an action is not at our disposal.

Instead our algorithms utilize an approximate reset, which we show always exists. There are a few subtle points when designing such a reset. First, we must select actions to achieve the approximate reset, i.e. the approximate reset is done through the use of a homing strategy. Hence, while homing, the agent is neither exploring nor exploiting. Second, rather than moving to a fixed state, the homing strategy can only hope to move to toward a fixed (unknown) belief state. Third, as we shall see, since the POMDP might be periodic the stopping time must be a random variable 1 . To implement this randomized stopping time, we introduce fictitious 'stay' actions, in which the agent does not take an action that period. By this, we mean that if the homing strategy decides to take a 'stay' action at some time -which may not be possible if the true POMDP does not permit 'stay' actions - then the agent just ignores this 'stay' action and obtains another action from the homing strategy to execute. Hence, after the agent has taken t homing actions (which are either real or 'stay' actions), the agent has taken t -m real actions in the POMDP and m stay actions. We now define an approximate reset strategy.

Definition 3.1 H is an (ϵ, k)-approximate reset (or homing) strategy if for every two belief states B1 and B2, we have ‖HE(B1) -HE(B2)‖1 ≤ ϵ, where HE(B) is the expected belief state reached from B after k homing actions of H (so at most k real actions have been taken) and H(B) is a random variable such that HE(B) = EH(B)∼H,B[H(B)].

The above definition only states that H will approximately reset, but this approximation quality could be poor. We now show how to amplify the accuracy of an approximate homing strategy, and then we show that an approximate homing strategy always exists.

Lemma 3.1 Suppose that H is an (ϵ, k) approximate reset then Hℓ is an (ϵℓ , kℓ) approximate reset, where Hℓ consecutively implements H for ℓ times. Furthermore, this implies there exists a unique belief state BH such that HE(BH) = BH .

Proof: The proof is a standard contraction argument, and we use induction. For l = 1, the claim follows by definition. Assume now that ‖Hℓ-1 E (B1) -Hℓ-1 E (B2)‖1 ≤ ϵℓ-1 . Let Hl-1 E (B1) = Q1 and Hl-1 E (B2) = Q2, so ∑s |Q1(s) - Q2(s)| ≤ ϵℓ-1 . For an arbitrary state s′ , and using the fact that H is a linear operator, we have

1 Without randomizing over the stopping times (i.e. allowing 'stay' actions), the state transition matrix may be periodic and no stationary distribution may exist, e.g. if the states deterministically alternate between states 1 and 2.

‖HℓE (B1) - HℓE (B2)]‖1 = ‖HE(Q1) -HE(Q2)]‖1 = ‖ ∑ s (Q1(s) - Q2(s))HE (s)‖1 = ‖ ∑ s (Q1(s) - Q2(s))HE(s′ )‖1 +‖ ∑ s (Q1(s) - Q2(s))(HE(s) - HE(s′ ))‖1 = 0+ ∑ s |Q1(s) - Q2(s)|ϵ ≤ ϵℓ

where the first term is 0 since for any two distributions ∑s Q1(s) - Q2(s) = 1 - 1 = 0 (and the vector H(s′ ) is constant in this sum), and we have used the fact that ‖H(s) - H(s′ )‖1 ≤ ϵ (by definition of H). □

We now show that the random walk strategy (including 'stay' actions) is an approximate reset strategy in every POMDP (including periodic ones), though with prior knowledge we might have better approximate reset strategies at our disposal.

Lemma 3.2 For all POMDPs, the random walk strategy (using 'stay' actions) constitutes an (ϵ, k) approximate reset strategy for some k ≥ 1 and 0 < ϵ < 12 .

Proof: By our connectivity assumption, for all states s and s′ , there exists some strategy that reaches s′ from s with positive probability. This implies that under H (the random walk strategy), there is positive probability of moving from one state to another, i.e. the Markov chain is irreducible. Furthermore, since H performs 'stay' actions, then the Markov chain is aperiodic. Thus, there exists a unique stationary distribution. We choose k to be the time at which the error in convergence is less than 1/2, from all starting states. Hence, by linearity of expectation, the error is less than 1/2 from all belief states in k steps. □

4 Reinforcement Learning with Homing

We now provide two algorithms which demonstrate how near-optimal average reward can be obtained, with different rates of convergence. The key to the success of these algorithms is their use of homing sequences in both exploration and in exploitation. For exploration, the idea is that each time we attempt some exploration trajectory we do it after implementing our reset strategy - hence our information is (approximately) grounded with respect to the belief state BH (recall HE(BH) = BH). The idea of exploration is to find a good t-Markov strategy ˆπ∗ t from BH. During exploitation, the goal is to use this t-Markov strategy. Unfortunately, we have only guaranteed that ˆπ∗ t performs well starting fromBH and only for t steps. Hence, after each time we exploit with ˆπ∗T , we run our homing sequence to get back close to BH (and then we rerun ˆπ∗ t ). We gradually increase t in the process.

The problem is that while homing, we are wasting time and neither exploiting nor exploring. Furthermore, since we use

Input : H /*a (1/2,KH) approximate reset strategy */ for t = 1 to∞do /*Exploration in Phase t */; kt1 = O ( 1 ϵ2t log(t2 |Πt|)); foreach Policy π in Πt do for i = 1 to kt1 do Run π for t steps; Repeatedly run H for log(1/ϵt) times; end Let vπ be the average return of π in from these kt1 trials; end /*Exploitation in Phase t */; Let ˆπ∗ t = argmaxπ∈Πt vπ ; kt2 = O( 1 ϵt ([current time T] +[time in t + 1-th exploration phase])); for i = 1 to kt2 do Run ˆπ∗ t for t steps; Repeatedly run H for log(1/ϵt) times; end end

the homing sequence between every run of ˆπ∗ t , asymptotically we never stop homing. Nonetheless, we able to show that there exists an algorithm which obtains near optimal reward in a POMDP, since the ratio of the time spent exploiting vs. homing decreases sufficiently fast.

Theorem 4.1 There exists an algorithm A, such that in any connected POMDP, A obtains the optimal average reward in the limit, with probability 1.

We later provide an algorithm with a better convergence rate (see Theorem 4.5). However, we start with a simpler policy search algorithm which establishes the above Theorem.

4.1 Policy Search

Algorithm 1 takes as input a (1/2,KH)-approximate reset strategy, which could be the random walk strategy with a very crude reset. The algorithm works in phases, interleaving exploration phases with exploitation phases. Let us start by describing the exploration phases. Let Πt be the set of all t-Markov strategies. An estimate of the value of a policy π ∈ Πt can be found by first resetting and then running π for t steps. The exploration phase consists of obtaining an estimate vπ of the return of each policy π ∈ Πt, where each estimate consists of an average of k1 trials (followed by approximate resets).

These estimates have both bias and variance. The variance is just due to the stochastic nature of the POMDP. The bias is due to the fact that we never can exactly reset to BH. However, if we run H for log 1/ϵt times (where ϵt is an error parameter in the t-th phase, which will be fixed latter) then, by lemma 3.1, all expected belief states we could approach will be (1/2)log 1/ϵt = ϵt close to BH. The following lemma shows that accurate estimates can be obtained.

Lemma 4.2 In phase t, if kt1 = O ( 1 ϵ2t log(t2 |Πt|)) and each reset consists of using the homing sequence log 1/ϵt times, then for all policies π ∈ Πt, the estimated t-horizon reward, vπ , satisfies |Rπ t (BH) - vπ | ≤ 2ϵt with probability greater than 1- 1 2t2 .

Proof: First, let us deal with the bias. Any expected belief states b that results from using the homing sequence log 1/ϵt times must satisfy ‖b - BH‖ ≤ (1/2)log 1/ϵt ≤ ϵt. Now it is straightforward to see that if b and BH are belief states such that ‖b - BH‖1 ≤ ϵ, then for every strategy π, |Rπ t (b) - Rπ t (BH)| ≤ ϵ. To see this, let the belief states at time t be bt and BtH , which result from following either π starting from b or BH, respectively. By linearity of expectation, it follows that ‖bt - BtH ‖1 ≤ ϵ. This directly implies that |Rπ t (b) - Rπ t (BH)| ≤ ϵ.

For the variance, the Hoeffding bound and our choice of kt1 imply that the average return of each policy is ϵt close to its expectation (the expectation is both over the initial state and on the policy trajectory) with probability 1-1/(2t2 ). □

Now during exploitation, the algorithm uses the policy ˆπ∗ t which had the highest return in the exploration phase (and by the previous lemma this is close to the policy with largest return). Note that we have only guaranteed a large return for executing ˆπ∗ t fromBH for t steps. However, we would like to exploit for a longer period of time than t. The key is that we again reset log(1/ϵt) times after each time we run ˆπ∗ t , which resets us close ϵt close to BH. Unfortunately, this means we spend KH log 1/ϵt steps between each run of ˆπ∗ . Hence, our average return could be O( 1t KH log 1/ϵt) less than we would like, since O( 1t KH log 1/ϵt) is the fraction of time we spend resetting. Note that this fraction could be large if we desire that ϵt be very small (thought this would guarantee very accurate resets).

Now, when we do exploit (and reset), we run the exploitation phase long enough (for kt2 time) such that our overall average reward is comparable to the average reward in the last exploitation phase.

Lemma 4.3 At any time T after phase t, the average reward from time 1 to time T satisfies: 1 T ∑Ti=1 ri ≥ R∗ t (BH) - O(ϵt + 1t KH log(1/ϵt)) with probability at least 1 - 1 t2 .

Before proving this lemma, let us state a corollary from which Theorem 4.1 follows.

Importantly, note the loss term goes to 0 as t goes to infinity. Furthermore, for a large enough phase t, we know that R∗ t (BH) will approach the optimal average reward R∗ (since R∗ is independent of the starting B). Theorem 4.1 follows. Essentially, although we have to home infinitely often, the ratio of time spent homing to the time spent using our t-step exploitation policies is going as O( log t t ), which goes to 0.

Proof: First, let us show that the average reward, 1 T ∑Ti=1 ri ≥ R∗ t (BH), is no less than ϵt from the average reward obtained in the t-th exploitation phase. To do this, we set the time of exploitation phase, kt2 , to be 1/ϵt times greater than previous amount of time spent in the MDP time plus the amount of time that will be spent in the next exploration phase (this latter factor accounts for the case in which time T lies in the exploration phase immediately after t).

Now we bound the average reward obtained in the exploitation phase. First. let us show that the t-average reward of the policy used, Rˆπ∗ t t , satisfies R∗ t (BH) - Rˆπ∗ t t (BH) ≤ 4ϵt with probability at least 1 - 1 2t2 . By Lemma 4.2 for each policy π ∈ Πt, we have |Rπ t (BH) - vπ | ≤ 2ϵt with probability at least 1 - 1 2|Πt|t2 . Therefore, ˆπ∗ t is 4ϵt-optimal with probability 1-1/(2t2 ). Now the observed average return of ˆπ∗ t in the exploitation period is 2ϵt close to R∗ t (BH) with probability at least 1- 1 2t2 , since our observed average return in exploitation is least as good as those used to find v ˆπ∗ t (since kt2 > kt1 ).

However, the average return during the exploitation phase is not the observed average return of ˆπ∗ t , since we reset after each t exploitation steps for a number of steps that is KH log(1/ϵt). The resets in the exploitation period can change the average reward by at most a fraction 1t KH log(1/ϵt). □

4.2 AModel Based Algorithm

The previous algorithm was the simplest way to demonstrate Theorem 4.1. However, it is very inefficient, since it is testing all t-Markov policies - there are doubly exponential, in t, such polices 2 . Here, we provide a more efficient model based algorithm, which resembles the algorithms given in Kearns et al. (1999); McAllester and Singh (1999), and is exponential in the horizon time, yet it still has no dependence on the number of states in the POMDP.

We now state a convergence rate in terms of τ, the ϵhorizon time of an optimal policy (see Section 2) and and in terms of the homing time KH (recall, such a time exists for every POMDP using a random walk policy).

Theorem 4.5 There exists an algorithm A, such that in any connected POMDP and with probability greater than 1 - δ, A achieves an average reward that is 2ϵ close to the optimal average reward in a number of steps in the POMDP which is polynomial in |A|,|O|,KH and log(1/δ) and exponential in τ. Furthermore the computational runtime of this algorithm is polynomial in |A|,|O|, and log(1/δ) and exponential τ.

We provide such an algorithm in the next page. In exploration phase, the algorithm builds an approximate model of the transition probabilities after some history has occurred starting from BH. In the t-th phase, it builds a model with respect to the set of all t-length histories, which we denote by Ht. In the exploitation phase, it uses the best t Markov strategy with respect to this model. The use of homing strategies is similar to that in the previous algorithm.

Let L = |A||O|, and note that 2Lt ≥ |Ht|. In the exploration phase, the algorithm takes actions uniformly at random for t steps and then resets (running the homing strategy

2 The number of histories of length t is exponential in t, and the number of t-Markov polices is exponential in the number of t-length histories

Input : H /*an (1/2,KH) approximate reset strategy */ Let L = |A| · |O|; for t = 1 to∞do kt1 = O ( L4t ϵ2t log(t2 |Ht|)); for kt1 times do Run RANDOM for t steps; Run H for KH log(Lt/ϵt) steps. end for h ∈ Ht, a ∈ A and o ∈ O do ˆ Pr[o|h, B0, a] = 0; if ˆ Pr[h(a, o)|B0] ≥ ϵt Lt then ˆ Pr[o|h,B0, a] = ˆ Pr[h(a,o)|B0] ˆ Pr[h|B0] ˆ Pr[a] end end Compute ˆπ∗ t using ˆ Pr[o|B0, h, a]; kt2 = O( 1 ϵt ([current time T] +[time in t + 1-th exploration phase])); for kt2 times do Run ˆπ∗ t for t steps; Run H for KHlog(1/ϵt) steps; end end

for log(Lt/ϵt) times). This is done kt1 times. 3 Then using the empirical frequencies in these trajectories the algorithm forms estimates ˆ Pr[o|h,BH, a], which is just the empirical probability of observing o conditioned on history h followed by taking action a. For histories h which are unlikely, these empirical estimates could be very bad, though, as we shall see, we do not need accurate estimates of ˆ Pr[o|h,BH, a] for such histories. Let h(a, o) be a history with h followed by (a, o).

Lemma 4.6 In phase t, if kt1 = O ( L4t ϵ2t log(t2 |Ht|)) and each reset consists of using the homing sequence log(Lt/ϵt) times, then: (1) | ˆ Pr[h|B0] - Pr[h|B0]| ≤ ϵt L2t , and (2) for every h(a, o) ∈ Ht such that Pr[h(a, o)|B0] ≥ ϵt Lt , we have | ˆ Pr[o|h, B0, a] - Pr[o|h, B0, a]| ≤ 2|A| Lt , with probability at least 1- 1 t2 .

Proof: We first note that, with probability 1 - 1/t2 , for every history h ∈ Ht we have | ˆ Pr[h|B0] -Pr[h|B0]| ≤ ϵt L2t (using the Hoeffding bound). The error, |Pr[o|h,B0, a] -

3 We can use in the algorithm any approximate homing strategy H. However, if H is simply the random policy, then the reset and exploration would both use the same policy, and the algorithm would slightly simplify.

ˆ Pr[o|h,B0, a]|, is then

where the first inequality holds with probability 1 - 1 t2 , and in the last inequality we used the fact that Pr[h|B0] ≥ ϵt Lt . □

The exploitation policy can be found using dynamic programming with the model. Note that the POMDP is equivalent to an MDP where the histories are states. In the exploitation phase, the algorithm uses the best t-Markov policy, ˆπ∗ t , (with respect to the approximate model) interleaving it with KH log(1/ϵt) homing steps.

Lemma 4.7 In phase t, the exploitation policy ˆπ∗ t , satisfies |R∗ t (BH) - Rˆπ∗ t t (BH)| ≤ t(ϵt + 2|A| Lt ) + (2ϵt + 2ϵt Lt ) with probability at least 1- 1 t2 .

Proof: (sketch) We observe that by ignoring all histories (which we view as nodes in a tree) such that ˆ Pr(h|B0) ≤ ϵt Lt , the return of an optimal strategy in this empirical model is decreased by at most 2t(ϵt + ϵt Lt ), due to the fact that the true history probability is bounded by ϵt Lt + ϵt L2t , the return from each node is bounded by t and the total number of such nodes is bounded by 2Lt . Next we prove that the return of the optimal policy in the empirical model loses at most t2 (ϵt + 2|A| Lt ) due to the tree approximation on the other nodes (the other histories). Using backward induction, we show that the policy ˆπ∗ t has return not less than k2 (ϵt + 2|A| Lt ) in comparison to the true optimal value, starting from (t - k + 1)-length histories. The base case, for the leaves (the t-length histories), holds since the reward (which is encoded through the observations) is within ϵt + 2|A| Lt , where the first error is due to the imperfect reset and the second is due to the marginal distribution error that is bounded by 2|A| Lt by Lemma 4.6. Assume the induction assumption holds for k - 1. There are two sources of error, the first is due to the current estimation error (of both the marginal distribution and the immediate reward) which is bounded by (ϵt + 2|A| Lt )k and the second is due to errors from the previous levels and is bounded by (k - 1)2 (ϵt + 2|A| Lt ) by the induction assumption. Summing the terms completes the induction step. □

Similarly to Subsection 4.1, we exploit long enough such that the overall average reward is essentially the average reward in the last exploitation period.

Lemma 4.8 At any time T after phase t, the average reward from time 1 to time T satisfies: 1 T ∑Ti=1 ri ≥ R∗ t (BH) - O(tϵt + |A|t Lt + (1/t)KH log(1/ϵt)) with probability at least 1- 1 t2 .

Using the above lemma, Theorem 4.5 follows immediately if we set ϵt = 1/t2 .

Proof: (sketch) We first note that all exploitations and explorations from phases 1 to T and from the next, (T + 1)-th, exploration phase can effect the average reward by at most ϵt. By Lemma 4.7, the exploitation policy is near optimal and satisfies, |R∗ t (BH) - Rˆπ∗ t t (BH)| ≤ t(ϵt + 2|A| Lt ) + (ϵt + ϵt Lt ) with probability 1 - 1/(2t2 ). As in Lemma 4.2, we observe that the bias of the exploitation policy is ϵt and the variance due to Hoeffding's bound and the large exploitation time is bounded by ϵt with probability 1 - 1/(2t2 ). The last source for loss is the resets in the exploitation period and its effect can be bounded by KH log(1/ϵt) t . □

A direct and simple corollary from which Theorem 4.1 follows as well.

Corollary 4.9 Let ϵt = 1/t. Then 1 T ∑Ti=1 ri ≥ R∗ t (BH) - O( KH log(t) t ) with probability at least 1 - 1 t2 .

Acknowledgements

This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778, and by a grant from the Israel Science Foundation and an IBM faculty award. This publication only reflects the authors' views.