Prior-Free Exploration Bonus for and beyond Near Bayes-Optimal Behavior

1 Introduction

One of the chief challenges in reinforcement learning (RL) [Sutton and Barto, 1998] is the exploration-exploitation trade-off; in RL, an agent needs to explore the world in order to gain new knowledge while it must exploit its current knowledge to earn rewards. One elegant solution for this dilemma is Bayesian RL, in which the agent considers the exploitation of possible future knowledge. Because of this consideration, the agent naturally explores in order to exploit its potential future knowledge. However, in general, such a Bayesian planning is intractable and requires approximation, for example, with the Monte-Carlo method [Wang et al., 2005; Asmuth and Littman, 2011; Browne et al., 2012].

A computationally cheaper way to approximate Bayesian planning is to modify a reward function (or a transition function) to force an agent to explicitly explore. It was shown that a simple algorithm can achieve near Bayesian optimal behavior in polynomial time in this way [Kolter and Ng, 2009]. However, the algorithm works only with an independent Dirichlet prior and a known reward function.

Along this line, several researchers developed more generally applicable algorithms. Yet, some have achieved only

Hiroshi Sato

National Defense Academy of Japan, Japan hsato@nda.ac.jp

PAC-MDP behavior [Sorg et al., 2010] and only in very limited cases [Sorg et al., 2010; Araya-López et al., 2012]. To the best of our knowledge, those algorithms have assured polynomial sample complexity for desired behaviors only with Dirichlet priors.

In this paper, we propose a novel algorithm that can achieve near Bayesian optimal policy in polynomial time for any priors that are not greatly misspecified. In addition, we will discuss and demonstrate that our proposed algorithm not only is more widely applicable, but also performs better than previous algorithms in many cases.

2 Method

A Markov Decision Process (MDP) [Puterman, 1994] is a tuple {S, A, R, P, ⌡} where S is a set of states, A is a set of actions, and P is a transition probability function that maps a state and an action to a probability of an agent transitioning to a new state. Also, R is a reward function that defines rewards for each state-action pair, and ⌡ is a discount factor.

2.1 Bayesian Reinforcement Learning

In a situation where the reward and transition probability functions are unknown, the agent needs to estimate them from its experience. A straightforward way to do this is to use Maximum Likelihood Estimation (MLE) based on the frequentist approach. However, an agent with mere MLE can fall into a sub-optimal policy, because the agent may not explore a state-action pair that was once incorrectly judged to have a low value [Strens, 2000]. This is due to the fact that the agent with MLE does not consider its estimation's uncertainty while planning [Meuleau and Bourgine, 1999].

One elegant solution is the Bayesian approach, which explicitly represents epistemic uncertainty by introducing the probability distribution over models b as the agent's belief. In full Bayesian planning, the agent recognizes the transition of its belief b as well as that of the state s defined in MDP. Trying to maximize expected rewards while planning, the agent plans in accordance with the following means:

• (a) ( , , ) : ( , ) [ ( , )] ( , ) R b s a R s a b R s a dR s a _ ⎢ and,
• (b) ( | , , ) : ( | , ) [ ( | , )] ( | , ) P s b s a P s s a b P s s a dP s s a _ ζ ζ ζ ζ ⎢ . Concretely, the agent plans by using the following value function [Duff, 2002]:

where sγ is the potential next state transitioned to from the current state s, and bγ is the possible belief updated to when a reward and a transition are observed with the current belief b.

As can be seen, the Bayesian optimal agent with the value function in equation (1) can naturally account for potential incorrectness in its current belief by considering possible future beliefs bγ. Hence, the agent can effectively explore while exploiting the current belief. However, as the number of possible belief states is typically very large, full Bayesian planning with equation (1) is intractable in most cases. Therefore, some approximation is required.

2.2 Exploitation plus Exploration Bonus

Because the intractability of Bayesian planning comes from the consideration of possible future beliefs, we can solve the problem simply by disregarding it. That is, we can use

However, we are now facing exactly the same problem that we had with MLE, which was that the agent does not choose to explore. Indeed, one can use any strategy that has been used for MLE to force the agent to explore. In particular, we will use the reward bonus function Rγ and let the agent use the following internal value function while planning:

where R � is defined to be the reward function R plus the reward bonus function Rγ.

The MLE version of an internal value function similar to equation (2) was used by Model Based Interval Estimation with Exploration Bonus (MBIE-EB) [Strehl et al., 2008]. MBIE-EB can ensure that the agent follows PAC-MDP behavior [Brafman and Tennenholtz, 2003; Strehl, 2007], but it does not utilize prior information. In order to make use of prior information, equation (2), which is an approximation of Bayesian planning, was used with the bonus being the posterior variance [Sorg et al., 2010]. For the sake of clarity, we refer to this algorithm as epistemic variance bonus (EVB). Although EVB can utilize information in prior belief efficiently, it aims to achieve PAC-MDP behavior similar to that of MBIE-EB. This is a notable disadvantage of EVB, because PAC-MDP algorithms show over-exploration despite prior knowledge and are not optimal in that sense.

Bayesian Exploration Bonus (BEB) [Kolter and Ng, 2009] is an existing algorithm in this line that can ensure that the agent will follow a near Bayesian optimal policy. However, it is only applicable to the special case of an independent Dirichlet prior and a known reward function.

2.3 Prior-Free Exploration Encouragement

We propose a new algorithm, called Prior Free Exploration Encouragement (PFEE). In order to guarantee high performance for different priors, PFEE uses a reward bonus, the exact form of which does not depend on the shapes of priors.

To do so, instead of focusing on posterior distribution (which is what related work has done), we pay attention to the history of the estimated means R(b) and P(b). Concretely, along with equation (2), PFEE uses the following bonus:

where ∩ is the adjustable parameter, n is the number of the most recent estimated means R(b) or P(b), and � 2 represents the variance of the n number of R(b) or P(b). The number n can be arbitrarily decreased to neglect the old information. Thus, the bonus Rγ tends to decrease as n is set to be larger, but the � 2 term penalizes it if the n recent estimated means differ from each other. In other words, equation (3) motivates the agent to explore the state-action pairs, for which the sequence of the estimated means has not yet converged.

Notice that both n and � 2 are defined in terms of the means estimated with sequential beliefs, while similar variables in previous work were characterized by observations or posterior distributions. Thus, n is not the number of observations used by MBIE-EB, nor is it counts as implied in BEB. For example, the initial value of the variable similar to n in MBIE-EB is 0, and in BEB it varies in accordance with the size of the Dirichlet prior. In contrast, a natural choice of n at the beginning of computation is 1, regardless of prior. This is because a designer initially assigns a prior to an agent, which usually makes the agent have '1' estimation value in its history. Also, the � 2 term is not the posterior variance used by EVB. For instance, the initial value of the variance in EVB varies based on the prior's shape, and it should not be 0 unless the agent is in a known MDP. However, the variance term of PFEE is initially 0 if n is equal to 1 as stated above.

The reason why we separated the term 1/(n+1) in equation (3) is to restrict the number of parameters �. Thus, we believe that its performance can be improved, if an additional parameter is added. However, in this paper, we use only equations (2) and (3) to maintain comparability with existing algorithms. For the same reason, we initialize n with 1 and set n to be equal to the number of all R(b) or P(b) in the agent's history: n = 1 + (the number of R(b) and P(b) updated).

3 Theoretical Results

This section provides a proof that an agent following PFEE will have a near Bayesian optimal policy in polynomial time for priors that are not greatly misspecified. Also, we discuss how PFEE behaves when priors are greatly misspecified. To prove the former, we first show that the agent always uses an internal value function higher than the Bayesian optimal value function, and then indicate that the internal value function will get close to the Bayesian value function as the agent gains experience. We will prove the first point with the following four Lemmas. Proofs of Lemma 1 through 4 can be found in appendix A.

Lemma 1. Let ( , , ) n R b s a be an average of n mean rewards estimated with n beliefs for a state-action pair. Then,

Note that in order to maintain simple representations, we made an assumption that will not affect the essential meaning of the final result: ( , , ) R b s a = [0,1]. For the same reason, we also define H to be the time horizon such that ⌡H » 0.

Lemma 2. Let ( ) , , Ο n R b s a be the standard deviation of n mean rewards estimated based on n beliefs. Then,

Lemma 3. Let ( , , ) n R b s a denote a mean reward estimated with the n-th belief for a state-action pair. Let � = 1/Γ� where Γ is any positive real number less than 1 and � represents a small quantity. Then,

As illustrated above, we deal with distributions of samples (for estimated means and variances), as well as with the probability distribution of a full population (for prior beliefs). However, when we talk about the distribution of samples, we do not focus on the underlying full population, from which the sample is made. Instead, we treat sampled points as the population of interest.

Lemma 4. Let ( | , , ) n P s b s a ζ and ( | ) , , Ο ζ n P s b s a be an average and a standard deviation of n mean transition probabilities estimated with n beliefs. Then with these, the bounds stated by Lemma 1 through 3 hold for the corresponding transition probability's variables as well.

Now, we are ready to provide the first important technical result.

Lemma 5. Let * ( , ) V b s and ( , ) V b s �� denote the optimal Bayesian value function and the value function used by PFEE (defined in equation (2) and (3)). Then, with the parameter � at least 2H� and with probability at least 1-4H|S||A|Γ,

Proof. Let n b be the n-th belief where n is the number of estimation values considered in the variance term of the bonus in PFEE. With probability at least 1-2H|S||A|Γ,

where 1 * 1 ( , ) n V b s 0 ζ is defined by the third line of the equation. In the equation above, the first line describes the definition. The second line follows Lemmas 3, 4 and the final step in the proof of Lemma 3 of [Sorg et al., 2010]. It holds true with probability at least 1-2Γ per belief updating for each stateaction pair.

Because 1 * ( , ) n V b s includes belief updating, what we need to do next is to exclude it as the following:

This inequality can be established by applying Lemmas 1, 2, and 4 for H Bayesian belief updates in the planning phase. Then, with the above definition of 2 * ( , ) n V b s ,

with probability at least 1-2 H|S||A|Γ. The first inequality is shown by Lemma 3 with probability at least 1-2Γ per belief updating for each state-action pair. The second inequality is true because � is not less than 1. Similarly, the third inequality holds, because H is at least 1. Summarizing the above, with probability at least 1-4H|S||A|Γ,

Another key insight behind PFEE is that an agent should follow Bayesian optimal policy only when the agent's belief is reliable. We will define misleading and non-misleading prior distributions based on whether or not a reliable belief can be obtained in a large number of time steps. As it is natural to say that the agent's belief is reliable when the estimated values' variance gets close to 0, we will define the types of priors as the following.

Definition 1. Let � 2 denote variances of estimation values regarding both rewards and transition probability. A prior distribution is said to be misleading if � 2]� /H 2 � when n=H 2 �/� . Otherwise, if � 2δ� /H 2 � when n=H 2 �/� , the prior distribution is said to be non-misleading.

Finally, we can show one of the main results in this section.

Theorem 1. Let ( , ) V b s � denote the value function described in equation (1) with a policy of PFEE rather than with a Bayesian optimal policy. Suppose that the agent updates its belief only until n=H 2 �/� . Let Γ be equal to �/4|S||A|H. Then by using a non-misleading prior, PFEE will follow a policy that is 13� -close to the Bayesian optimal policy in polynomial time with probability at least 1 - 2�:

Proof. Let K be a subset of states, on each of which the agent has n=H 2 �/� estimated mean values. Accordingly, define

( , ) K V b s � � as the value function that is equal to the bonusexcluded value function ( , ) V b s � on K and equal to the bonus-included value function ( , ) V b s �� elsewhere. In addition, let AK be the event where ( , ) K V b s � � becomes equal to ( , ) V b s �� . We first show the relationship of ( , ) V b s � and ( , ) K V b s � � . We can limit the upper bound of PFEE's bonus by the maximum reward value H to maintain optimism described in Lemma 5. Thus, by following Lemma 5 of [Kolter and Ng, 2009], for the time horizon H,

Secondly, we describe the bound for ( , ) K V b s � � and ( , ) V b s �� , which will be the bonus term with n=H 2 �/� for H time steps,

Finally, when P(AK)δ � /H 2 , with probability at least 1-2�,

The first line uses equation (4), the second line follows the assumption of P(AK)δ � /H 2 , the third line uses equation (5), and the fourth line follows Lemma 5. Thus, PFEE follows a policy 13� -close to Bayesian optimal policy when P(AK)δ � /H 2 . Otherwise, when P(AK) ] � /H 2 , by Hoeffding's inequality, n will be greater than or equal to n = H 2 �/� at least after

time steps with probability at least 1 - �. Then, after the time steps, by a strategy similar to the above,

with probability at least 1-2�. �

Now that we have discussed the behavior of PFEE only for non-misleading priors, we will consider its general behavior for all types of priors.

Lemma 6. Define B� and BEVB to be the bonus' variance term of PFEE and the posterior variance bonus used in EVB respectively. Let ( ) V s be the objective (true) value function of an MDP. Then for any prior,

with high probability and in polynomial time.

Proof. The first line follows theorem 1, and the second line follows the proof of Lemma 3 in [Sorg et al., 2010]. �

Lemma 6 well represents PFEE's performance. Notice that B� gets close to 0 when the prior is non-misleading, but BEVB cannot be 0 unless the posterior distribution has converged on one point of value. Thus, for any non-misleading priors, PFEE can use the value function close to the Bayesian optimal function * ( , ) V b s , while EVB cannot. On the other hand, when the prior is misleading (the first line of the equation with B�′0), PFEE forces an agent to keep exploring. This is a preferable property of PFEE, because it means that PFEE takes advantage of prior information only when it is useful.

Definition 2. Define the term completely misleading prior such that with that prior, B� is almost always higher than BEVB, and B� gets close to 0 only after BEVB goes to 0.

Corollary 1. For completely misleading priors, PFEE will follow PAC-MDP behavior if EVB does so.

Corollary 1 is implied by Lemma 6. If B� gets close to 0 when BEVB goes to 0, it is already the time when PFEE's value function becomes close to the true value function. This happens when EVB achieves PAC-MDP behavior.

Moreover, Lemma 6 implies that if the prior is misleading but not completely misleading, PFEE will have a greediness that is better balanced than PAC-MDP and a near Bayesian optimal strategy. This is because an agent with PFEE continues to explore if the prior is misleading (less greedy than misleading belief-oriented Bayes optimal behavior), but stops doing so and follows near Bayesian optimal policy when its belief becomes reliable (when B� gets close to 0) (greedier than over-exploring PAC-MDP).

4 Experimental Results

In this section, we present the practical performance of PFEE and other existing algorithms in the 5-state chain world, which is a standard benchmark problem in the literature. In the chain world, there are 5 states, S1 through S5, and the agent initially exists in S1. In all states, the agent can choose two actions, going to Si+1 from Si (where i+1ο5 if i = 5), or returning to S1. But, with probability 0.2, the agent "slips" and performs the opposite action as intended. Rewards are 0.2 for returning to S1, 1.0 for going to S5 from S5, and 0 otherwise. Although optimal policy is to choose to move toward S5 in all states, this setting encourages non-exploring agents to settle on S1. For more information on the chain problem, see [Strens, 2000]. To make our results comparable with previously published results, we report the algorithms' performances by showing total rewards in the first 1000 steps.

Table 1 shows the algorithms' average performances in 10 5 runs, along with the standard errors, for different sizes of uniform prior (i.e., full prior used in [Poupart, 2006]). Since true transition probabilities are not uniform, the large size of uniform prior (3|S|) is likely a (not completely but) misleading prior, and others (0.001 and 1) are expected to be non-misleading. The total rewards of more than 300 are underlined. The parameter ↔p of each algorithm is optimized in the same way that previous work adopted, and the optimum ↔p was estimated to be 2.5 for MBIE-EB and BEB (indeed, this is the same value reported in [Kolter and Ng, 2009]), 2.0 for EVB, and 2.2 for PFEE. Table 1 illustrates several points. First, BEB can outperform PAC-MDP (EVB and MBIE-EB in this case) when the prior is not greatly misspecified (i.e. when the prior size is 0.001 or 1). This is because the bonus in BEB decreases at the rate O(1/c), where c denotes the number of counts in a prior. This is faster than PAC-MDP's rate O( 1/ c ), and hence an agent following BEB is greedier than an agent following PAC-MDP algorithms. Second, EVB outperformed BEB when the prior was greatly misspecified (i.e. when the prior size is 3|S|=15). The reason for this is the same as for the case above: an agent following BEB is greedier with its belief, which in this case is incorrect to a large degree. Finally, while PFEE performed almost as well as BEB when the prior was not greatly misspecified, it outperformed other algorithms when the prior was greatly misspecified (i.e. when the size of uniform prior was 3|S|). This is what we inferred in the previous section: PFEE will follow Bayesian optimal policy in polynomial time for a non-misleading prior, and can perform better than PAC-MDP and Bayesian optimal behavior for a (not completely but) misleading prior. More concretely for this case, the first term of PFEE's bonus, 1/(n+1), decreases at the same rate as BEB's bonus, and thereby PFEE is similarly as greedy as BEB when its bonus' variance term is negligible. This is when the prior is non-misleading. Otherwise, when the prior is misleading, an agent following PFEE keeps exploring effectively, unlike BEB, because of the variance term of its bonus. Thus, PFEE outperformed PAC-MDP and at the same time worked better than BEB in a wider variety of cases.

In order to illustrate the versatility of PFEE more directly, we show the performances of PFEE and EVB for various sizes of uniform prior and values of parameter ↔p in Figures 1 and 2. The 10 5 runs' results are averaged in the figures. PFEE achieved total rewards of more than 340 when the prior size is 10 -3 to 10 0.5 , while EVB did so only for 10 -0.5 to 10 0.5 .

The fact that PFEE can handle misspecified priors better than existing algorithms does not mean that PFEE has an inferior ability to utilize informative priors. Figure 3 shows performances of each algorithm with optimized parameter ↔p for different sizes of informative prior. Here, the informative prior is defined as: 0.001 + (the true transition probabilities) φ(prior's sizes indicated on the x-axis of Figure 3). A similar way to construct informative priors was used in [Poupart, 2006]. The results shown are total rewards averaged over 10 4 runs for each prior size, and prior sizes cj are set such that cj+1 = cj + cjφ0.25 from c = 0.001 to cδ100 (i.e. the number of the markers in the figure are much less than those of actual data points). As can be seen, PFEE again outperformed existing algorithms. In fact, this result makes sense intuitively, as PFEE's bonus (variance term) can indirectly exploit the information built in the informative priors, while BEB's cannot. BEB's bonus utilizes only the amount of information (i.e., the number of counts). EVB's bonus can use that information more directly, but an agent following EVB overexplores when the amount of information is not very large.

5 Conclusion

In this paper, we introduced a new algorithm called PFEE, with which an agent will follow near Bayesian optimal policy in polynomial time for any non-misleading prior (with appropriate parameter values). We derived the algorithm by paying attention to the sequences of the estimated mean values. Regardless of prior, some of the sequences' properties hold true and we utilized this fact to limit its sample complexity for different types of priors.

Perhaps even more importantly, we showed that there are preferable consequences of focusing on the sequences of means generated in the Bayesian setting. Concretely, for completely misleading priors, PFEE will follow PAC-MDP in polynomial time at least when the previous algorithm (EVB) does so. Also, for misleading but not completely misleading priors, PFEE will explore until the belief becomes reliable and then follow Bayesian optimal policy. Thus, PFEE not only utilizes prior information efficiently if it is useful, but also avoids being misled by incorrect beliefs and keeps exploring to make sure to gain a reliable belief.

We demonstrated the above points in the standard chain problem. PFEE outperformed EVB and worked as well as BEB, and in many cases surpassed BEB. PFEE worked better than BEB when the prior is misspecified or informative.

It should be noted that in this paper, we set the number of estimated mean values n to be 1 + (the number of the means estimated) as the simplest configuration. Thus, as future work, one may improve PFEE's performance by adjusting that number based on some criteria. Also, a performance similar to PFEE would be expected for a future algorithm based on PAC-Bayes bounds [Fard and Pineau, 2010], and thus it will be interesting to compare these when such an algorithm becomes available.

A Technical Proofs

This appendix presents the proofs of Lemma 1 through 4 in that order. To make representations concise, we omit the arguments for state-action pairs.

Proof. (of Lemma 1) Let ( ) n R b be an average of n mean reward values estimated with n beliefs. Then,

The first equality is followed by the definition and the rest can be shown by algebraic manipulations. The last inequality is based on the assumption that R(b) = [0,1]. �

Proof. (of Lemma 2) Let ( ) Ο n R b be a standard deviation of n mean rewards estimated with n beliefs. Then,

The first equality is followed by the definition, and the second equality can be shown by algebraic manipulations. The last inequality can be derived with the assumption of R(b) = [0,1]. Notice that in the absolute value in the third line, there are only two underlying variables ∆R(b) and R(bn+1) that can affect the absolute value. When these two variables have a huge difference, the left-hand side of the equation gets close to 1/(n+1). �

Proof. (of Lemma 3) By using Chebyshev's inequality,

and

Note that if we had cared about X, from which the sample R(bn) would have been weakly exchangeably drawn (this assumption itself is likely unrealistic), then we would have had the following (see [Kabán, 2011]):

But, this is not the case. Hence, we use equations (A1) and (A2). When � 2υ 2Γ � , based on equation (A1),

On the other hand, when � 2? 2Γ � , with equation (A2),

Therefore,

Proof Sketch. (of Lemma 4) One can show the same results of Lemmas 1 to 3 for transition probabilities by using this appendix's equations with R(b) substituted by ∆sζP(sζ|b) and by noticing two points: the commutative law of addition holds for ∆sζ and ∆i, and ∆sζP(sζ|b) = 1 (in the usual case) or ∆sζP(sζ|b) = 0 (this may not make sense in the setting of MDP, but it is not prohibited for an agent to plan in this way). �