Mauricio Araya-López

Vincent Thomas

Olivier Buffet

Near-Optimal BRL using Optimistic Local Transitions (Extended Version)

Keywords: Bayesian Reinforcement Learning, Optimistic Algorithms, PAC-MDP BRL Quasi-Optimal Apprentissage par renforcement bayésien, Algorithmes optimistes, PAC-MDP

Model-based Bayesian Reinforcement Learning (BRL) allows a sound formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work relies on heuristic algorithms. This paper introduces bolt, a simple and (almost) deterministic heuristic algorithm for BRL which is optimistic about the transition function. We analyze bolt's sample complexity, and show that under certain parameters, the algorithm is near-optimal in the Bayesian sense with high probability. Then, experimental results highlight the key differences of this method compared to previous work.

Introduction

Acting in an unknown environment requires trading off exploration (acting so as to acquire knowledge) and exploitation (acting so as to maximize expected return). Model-Based Bayesian Reinforcement Learning (BRL) algorithms achieve this while maintaining and using a probability distribution over possible models (which requires expert knowledge under the form of a prior).These algorithms typically fall within one of the three following classes [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF].

Belief-lookahead approaches try to optimally trade off exploration and exploitation by reformulating RL as the problem of solving a POMDP where the state is a pair ω = (s, b), s being the observed state and b the distribution over the possible models; yet, this problem is intractable, allowing only computationally expensive approximate solutions [START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF] [START_REF] Dimitrakakis | Tree exploration for Bayesian RL exploration[END_REF].

Optimistic approaches propose exploration mechanisms that explicitly attempt to reduce the model uncertainty [START_REF] Brafman | R-max -a general polynomial time algorithm for near-optimal reinforcement learning[END_REF][START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF][START_REF] Sorg | Variance-based rewards for approximate Bayesian reinforcement learning[END_REF][START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF] by relying on the principle of "optimism in the face of uncertainty".

Undirected approaches, such as -greedy or Boltzmann exploration strategies [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]], perform exploration actions independent of the current knowledge about the environment.

We focus here on optimistic approaches and, as most research in the field and without loss of generality, we consider uncertainty on the transition function, assuming a known reward function. For some algorithms, recent work proves that they are either PAC-MDP [START_REF] Strehl | Reinforcement learning in finite MDPs: PAC analysis[END_REF]with high probability they often act as an optimal policy would do (if the MDP model were known)-or PAC-BAMDP [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF]-with high probability they often act as an ideal belief-lookahead algorithm would do.

This paper first presents background on model-based BRL in Section 2, and on PAC-MDP and PAC-BAMDP analysis in Section 3. Then, Section 4 introduces a novel algorithm, bolt, which, (1) as boss [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF], is optimistic about the transition model-which is intuitively appealing since the uncertainty is about the model-and, (2) as beb [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], is (almost) deterministic-which leads to a better control over this approach. We then prove in Section 5 that bolt is PAC-BAMDP for infinite horizons, by generalizing previous results known for beb for finite horizon. Experiments in Section 6 then give some insight as to the practical behavior of these algorithms, showing in particular that bolt seems less sensitive to parameter tuning than beb. Due to space constraints and clarity, we have deferred all proofs of lemmas to the appendix, keeping the main proofs of the theorems.

Background

Reinforcement Learning

A Markov Decision Process (MDP) [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] is defined by a tuple S, A, T, R where S is a finite set of states, A is a finite set of actions, the transition function T is the probability to transition from state s to state s when some action a is performed: T (s, a, s ) = P r(s |s, a), and R(s, a, s ) is the instant scalar reward obtained during this transition. Reinforcement Learning (RL) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] is the problem of finding an optimal decision policy-a mapping π : S → A-when the model (T without R in our case) is unknown but while interacting with Inria the system. A typical performance criterion is the expected discounted return

V π µ (s) = E π ∞ t=0 γ t R(s t , a t , s t+1 ) | s 0 = s, T = µ ,
where µ ∈ M is the unknown model and γ ∈ [0, 1] is a discount factor. In this paper we do not account for uncertainty about the reward function as it can be turned into an uncertainty about the transition function, meaning that only T is unknown and R is given. Under an optimal policy, this state value function verifies the Bellman optimality equation [START_REF] Bellman | The theory of dynamic programming[END_REF] (for all s ∈ S):

V * µ (s) = max a∈A s ∈S T (s, a, s ) R(s, a, s ) + γV * µ (s ) ,
and computing this optimal value function allows to derive an optimal policy by behaving in a greedy manner, i.e., by picking actions in arg max a∈A Q * µ (s, a), where the state-action value function Q * µ is defined as

Q * µ (s, a) = s ∈S T (s, a, s ) R(s, a, s ) + γV * µ (s ) .
Typical RL algorithms either (i) directly estimate the optimal state-action value function

Q * µ (model-free RL), or (ii) learn T to compute V * µ or Q * µ (model-based RL
). Yet, in both cases, a major difficulty is to pick actions so as to trade off exploitation of the current knowledge and exploration to acquire more knowledge.

Model-based Bayesian RL

We consider here model-based Bayesian Reinforcement Learning [START_REF] Malcolm | A Bayesian framework for reinforcement learning[END_REF], i.e., model-based RL where the knowledge about the model is represented using a probability distribution b over all possible transition models. An initial prior distribution b 0 = P r(µ) has to be specified, which is then updated using Bayes rule. At time t the posterior b t depends on the initial distribution b 0 and the state-action history so far h t = s 0 , a 0 , • • • , s t-1 , a t-1 , s t . This update can be applied sequentially due to the Markov assumption, i.e., at time t + 1 we only need b t and the triplet (s t , a t , s t+1 ) to compute the new distribution:

b t+1 = P r(µ|h t+1 , b 0 ) = P r(µ|s t , a t , s t+1 , b t ).
(1)

The distribution b t is known as the belief over the model, and summarizes the information that we have gathered about the model at the current time step.

If we consider the belief as part of the state, the resulting belief-MDP over this multivariate infinite state space can be solved optimally in theory. Yet this is in practice intractable due to the increasing complexity along the planning horizon. Remarkably, modelling RL problems as belief-MDPs provides a sound way of dealing with the exploration-exploitation dilemma, because both objectives are naturally included in the same optimization criterion.

The belief-state can thus be written as ω = (s, b), which defines a Bayes-Adaptive MDP (BAMDP) 1 [START_REF] Duff | Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes[END_REF], a special kind of belief-MDP where the belief-state is factored into the (visible) system state and the belief over the (hidden) model. Moreover, due to the integration 1 BAMDP also stands for Belief-Augmented MDP [START_REF] Dimitrakakis | Tree exploration for Bayesian RL exploration[END_REF].

RR n°7965

over all possible models in the value function of the BAMDP, the transition function T (ω, a, ω ) is given by

P r(ω |ω, a) = P r(b |b, s, a, s )E[P r(s |s, a)|b],
where the first probability is 1 if b complies with Eq. ( 1) and 0 else. The optimal Bayesian policy can then be obtained by computing the optimal Bayesian value function [START_REF] Duff | Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes[END_REF][START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF]:

V * (s, b) = max a s E[P r(s |s, a)|b](R(s, a, s ) + γV * (s , b )) = max a s T (s, a, s , b)(R(s, a, s ) + γV * (s , b )) , (2)
with b the posterior after the Bayes update with (s, a, s ). For the finite horizon case we can use the same reasoning, so that the optimal value can be computed in theory for a finite or infinite horizon, by performing Bayes updates and computing expectations. However, in practice, computing this value function exactly is intractable due to the large branching factor of the tree expansion.

At first glance, is obvious to look at POMDP algorithms, because they also deal with belief-MDPs. Unfortunately, one cannot directly benefit from classical POMDP algorithms because of the infinite dimensional nature of the state space. Other-offline or online-approximate approaches have therefore been introduced, allowing in a number of cases to prove theoretical properties.

Here, we are interested in heuristic approaches following the optimism in the face of uncertainty principle, which consists in assuming a higher return on the most uncertain transitions. Some of them solve the MDP generated by the expected model (at some stage) with an added exploration reward which favors transitions with lesser known models, as in r-max [START_REF] Brafman | R-max -a general polynomial time algorithm for near-optimal reinforcement learning[END_REF], beb [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], or with variance based rewards [START_REF] Sorg | Variance-based rewards for approximate Bayesian reinforcement learning[END_REF]. Another approach, used in boss [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF], is to solve, when the model has changed sufficiently, an optimistic estimate of the true MDP (obtained by merging multiple sampled models).

Flat and Structured Priors

The selection of a suitable prior is an important issue in BRL algorithms, because it has a direct impact on the solution quality and computing time. A naive approach is to consider one independent Dirichlet distribution for each state-action transition, known as Flat-Dirichlet-Multinomial prior (FDM), whose pdf is defined as

b = f (µ; θ) = s,a D(µ s,a ; θ s,a ),
where D(•; •) are independent Dirichlet distributions. FDMs can be applied to any discrete state-action MDP, but is only appropriate under the strong assumption of independence of the state-action pairs in the transition function. However, this prior has been broadly used because of its simplicity for computing the Bayesian update and the expected value. Consider that the vector of parameters θ are the counters of observed transitions, then the expected value of Inria a transition probability is E[P r(s |s, a)|b] = θs,a(s ) s θs,a(s ) , and the Bayesian update under the evidence of a transition (s, a, s ), is reduced only to θ s,a (s ) = θ s,a (s ) + 1.

Even though FDMs are useful to analyze and benchmark algorithms, in practice they are inefficient because they do not exploit structured information about the problem. One can for example encode the fact that multiple actions share the same model by factoring multiple Dirichlet distributions, or allow the algorithm to identify such structures using Dirichlet distributions combined using Chinese Restaurant Processes or Indian Buffet Processes [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF]. Also, specific problems could lead to other families of distributions different from Dirichlet, for example the Bayesian distribution over deterministic MDPs presented by [START_REF] Sorg | Variance-based rewards for approximate Bayesian reinforcement learning[END_REF].

PAC Algorithms

Probably Approximately Correct Learning (PAC) provides a way of analyzing the quality of learning algorithms [START_REF] Valiant | A theory of the learnable[END_REF]. The general idea is that with high probability 1 -δ (probably), a machine with a low training error produces a low generalization error bounded by (approximately correct). If the number of steps needed to arrive to this condition is bounded by a polynomial function, then the algorithm is PAC-efficient.

PAC-MDP Analysis

In RL, the PAC-MDP property [START_REF] Strehl | Reinforcement learning in finite MDPs: PAC analysis[END_REF] guarantees that an algorithm generates an -close policy with probability 1-δ in all but a polynomial number of steps. The major difference with PAC Learning is that there is no guarantee on when the non--close steps will occur, but the number of non--close steps is bounded by a polynomial. An important result is the general PAC-MDP Theorem 10 in [START_REF] Strehl | Reinforcement learning in finite MDPs: PAC analysis[END_REF], where three sufficient conditions are presented to comply with the PAC-MDP property. First, the algorithm must use at least near optimistic values with high probability. Also, the algorithm must guarantee with high probability that it is accurate, meaning that, for the known parts of the model, its actual evaluation will be -close to the optimal value function. Finally, the number of non--close steps (also called sample complexity) must be bounded by a polynomial function.

In mathematical terms, PAC-MDP algorithms are those for which, with probability 1 -δ, the evaluation of a policy A t , generated by algorithm A at time t over the real underlying model µ 0 , is -close to the optimal policy over the same model in all but a polynomial number of steps:

V At µ0 (s) ≥ V * µ0 (s) -. (3)
Several RL algorithms comply with the PAC-MDP property, differing from one another mainly on the tightness of the sample complexity bound. For example, r-max [START_REF] Brafman | R-max -a general polynomial time algorithm for near-optimal reinforcement learning[END_REF], mbie-eb [START_REF] Strehl | A theoretical analysis of model-based interval estimation[END_REF] and Delayed Q-Learning [START_REF] Strehl | Reinforcement learning in finite MDPs: PAC analysis[END_REF] are some classic RL algorithms for which this property has been proved, whereas BOSS [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF]] is a Bayesian RL algorithm which is also PAC-MDP.

In PAC-MDP analysis the policy produced by an algorithm should be close to the optimal policy derived from the real underlying MDP model. This utopic policy [START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF]] cannot be computed, because it is impossible to learn exactly the model with a finite number of samples, but it is possible to reason on the probabilistic error bounds of an approximation to this policy.

In model-based RL, the exploration vs. exploitation dilemma arises as the compromise between producing accurate estimates of the real model (exploration), and optimally acting with respect to the current estimates (exploitation). Then, the correctness of an algorithm will depend on these two different criteria, which are impossible to combine without biasing the results to certain models.

PAC-BAMDP Analysis

An alternative to the PAC-MDP approach is to be PAC with respect to the optimal Bayesian policy, rather than using the optimal utopic policy. We will call this PAC-BAMDP analysis, because its aim is to guarantee closeness to the optimal solution of the Bayes-Adaptive MDP. This type of analysis was first introduced in Kolter and Ng [2009], under the name of near-Bayesian property, where it is shown that a modified version of beb is PAC-BAMDP for the undiscounted finite horizon case2 .

Let us define how to evaluate a policy in the Bayesian sense:

Definition 3.1. The Bayesian evaluation V of a policy π is the expected value given a distribution over models b:

V π (s, b) = E µ [V π µ (s)|b] = M V π µ (s)P r(µ|b)dµ.
This definition has already been presented implicitly by [START_REF] Duff | Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes[END_REF] and explicitly by Dimitrakakis [2008], but it is very important to point out the difference between a normal MDP evaluation over some known MDP, and the Bayesian evaluation3 . This definition is consistent with Eq. 2, where

V * (s, b) = max π M V π µ (s)P r(µ|b)dµ = max a s E[P r(s |s, a)|b](R(s, a, s ) + γV * (s , b )) .
Let us define the PAC-BAMDP property:

Definition 3.2. We say that an algorithm is PAC-BAMDP if, with probability 1-δ, the Bayesian evaluation of a policy A t generated by algorithm A at time t is -close to the optimal Bayesian policy in all but a polynomial number of steps, where the Bayesian evaluation is parametrized by the belief b:

V At (s, b) ≥ V * (s, b) -, (4)
with δ ∈ [0, 1) and > 0.

A major conceptual difference is that in PAC-BAMDP analysis, the objective is to guarantee approximate correctness because the optimal Bayesian policy is hard to compute, while in PAC-MDP analysis, the approximate correctness guarantee is needed because the optimal utopic policy is impossible to find in a finite number of steps.

Optimistic BRL Algorithms

Sec. 2.2 has shown how to theoretically compute the optimal Bayesian value function. This computation being intractable, it is common to use suboptimal-yet efficient-algorithms. A

Bayes update MDP MDP b t → b t+1 i i i + 1 i + 1 t t + 1 E[µ|b t ] ∞ E[µ|b t+1 ] 0 H H Figure 1: exploit-like algorithm.
At each time step t, algorithm performs a Bayes update of the prior, and solves the MDP derived from the expected model of the belief.

popular technique is to maintain a posterior over the belief, select one representative MDP based on the posterior and act according to its value function. The baseline algorithm in this family is called exploit [START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF], where the expected model of b is selected at each time step. Therefore, the algorithm has to solve a different MDP of horizon H-an algorithm parameter, not the problem horizon-at each time step t as can be seen in Fig. 1. We will consider for the analysis that H is the number of iterations i that value iteration performs at each time step t, but in practice convergence can be reached long before the theoretically derived H for the infinite horizon case.

beb [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF] follows the same idea as exploit, but adding an exploration bonus to the reward function. In contrast, boss [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF] does not use the exploit approach, but samples different models from the prior and uses them to construct an optimistic MDP. beb has the advantage of being an almost deterministic algorithm4 and does not rely on sampling as boss. On the other hand, boss is optimistic about the transitions, which is where the uncertainty lies, meanwhile beb is optimistic about the reward function, even though this function is known.

Bayesian Optimistic Local Transitions

In this section, we introduce a novel algorithm called bolt (Bayesian Optimistic Local Transitions), which relies on acting, at each time step t, by following the optimal policy for an optimistic variant of the current expected model. This variant is obtained by, for each state-action pair, optimistically boosting the Bayesian updates before computing the local expected transition model. This is achieved using a new MDP with an augmented action space A = A × S, where the transition model for action α = (a, σ) in state s is the local expected model derived from b t updated with an artificial evidence of transitions λ η s,a,σ = {(s, a, σ), . . . , (s, a, σ)} of size η (a parameter of the algorithm). In other words, we pick both an action a plus the next state σ we would like to occur with a higher probability. The MDP can be solved as follows:

V bolt i (s, b t ) = max α s T (s, α, s , b t ) R(s, a, s ) + γV bolt i-1 (s , b t ) with T (s, α, s ) = E[P r(s |s, a)|b t , λ η s,a,σ ].
bolt's value iteration neglects the evolution of b t , but the modified transition function works as an optimistic approximation of the neglected Bayesian evolution.

Modifying the transition function seems to be a more natural approach than modifying the reward function as in beb, since the uncertainty we consider in these problems is about the transition function, not about the reward function.

From a computational point of view, each update in bolt requires |S| times more computations than each update in beb. This implies computation times multiplied by |S| when solving finite horizon problems using dynamic programming, and probably a similar increase for value iteration. However, under structured priors, not all the next states σ must be explored, but only those which are possible transitions.

Here, the optimism is controlled by the positive parameter η-an integer or real-valued parameter depending on the family of distributions-and the behaviour using different parameter values will depend on the used family of distributions. However, for common priors like FDMs, it can be proved that bolt is always optimistic with respect to the optimal Bayesian value function.

Lemma 4.1 (bolt's Optimism). Let (s t , b t ) be the current belief-state from which we apply bolt's value iteration with an horizon of H and η = H. Let also b t be a prior in the FDM family, and let V H (s t , b t ) be the optimal Bayesian value function. Then, we have

V bolt H (s t , b t ) ≥ V H (s t , b t ).
[Proof in App. A.1]

Analysis of BOLT

In this section we prove that bolt is PAC-BAMDP in the discounted infinite horizon case5 solved at each step., when using a FDM prior. The other algorithm proved to be PAC-BAMDP is beb, but the analysis provided in [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF] is only for finite horizon domains with an imposed stopping condition for the Bayes update. Therefore, we include in App. B an analysis of beb using the results of this section in order to be able to compare these algorithms theoretically afterwards.

By Definition 3.2, we must analyze the policy A t generated by bolt at time t, i.e., A t = argmax π V bolt,π H (s t ), and show that, with high probability and for all but a polynomial number of steps, this policy is -close to the optimal Bayesian policy.

Theorem 5.1 (bolt is PAC-BAMDP). Let A t denote the policy followed by bolt at time t with η = H. Let also s t and b t be the corresponding state and belief at that time. Then, with probability at least 1 -δ, bolt is -close to the optimal Bayesian policy

V At (s t , b t ) ≥ V * (s t , b t ) - for all but Õ |S||A|η 2 2 (1-γ) 2 = Õ |S||A|H 2 2 (1-γ) 2 time steps. [Proof in Section 5.2]
In the proof we will see that H depends on and γ. Therefore, the sample complexity bound and the optimism parameter η will depend only on the desired correctness ( ,δ) and the problem characteristics (γ,|S|,|A|).

Mixed Value Function

To prove that bolt is PAC-BAMDP we introduce some preliminary concepts and results. First, let us assume for the analysis that we maintain a vector of transition counters θ, even though the priors may be different from FDMs for the specific lemma presented in this section. As the belief is monitored, at each step we can define a set K = {(s, a)| θ s,a ≥ m} of known state-action pairs [START_REF] Kearns | Near-optimal reinforcement learning in polynomial time[END_REF]], i.e., state-action pairs with "enough" evidence. Also, to analyze an exploit-like algorithm A in general (like exploit, bolt or beb) we introduce a mixed value function Ṽ obtained by performing an exact Bayesian update when a state-action pair is in K, and A's update when not in K. Using these concepts, we can revisit Lemma 5 of [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF] for the discounted case.

Lemma 5.2 (Induced Inequality Revisited). Let V π H (s t , b t ) be the Bayesian evaluation of a policy π, a = π(s, b) be an action from the policy. We define

Ṽπ i (s, b) = (5) s T (s, a, s , b)(R(s, a, s ) + γ Ṽπ i-1 (s , b )) if (s, a) ∈ K s T (s, a, s )( R(s, a, s ) + γ Ṽπ i-1 (s , b )) if (s, a) / ∈ K
the mixed value function, where T and R can be different from T and R respectively. Here, b is the posterior parameter vector after the Bayes update with (s, a, s ). Let also A K be the event that a pair (s, a) / ∈ K is generated for the first time when starting from state s t and following the policy π for H steps. Assuming normalized rewards for R and a maximum reward Rmax for R, then

V π H (s t , b t ) ≥ Ṽπ H (s t , b t ) - (1 -γ H ) (1 -γ) Rmax P r(A K ), (6)
where P r(A K ) is the probability of event A K .

[Proof in App. A.2]

BOLT is PAC-BAMDP

Let ṼAt H (s t , b t ) be the evaluation of bolt's policy A t using a mixed value function where R(s, a, s ) = R(s, a, s ) the reward function, and T (s, a, s ) = T (s, α, s , b t ) = E[P r(s |s, a)|b t , λ η s,a,σ ] the bolt transition model, where a and σ are obtained from the policy A t . Note that, even though we apply bolt's update, we still monitor the belief at each step as presented in Eq. 5.

Yet, for T we consider the belief at time t, and not the monitored belief b as in the Bayesian update Lemma 5.3 (bolt Mixed Bound). The difference between the optimistic value obtained by bolt and the Bayesian value obtained by the mixed value function under the policy A t generated by bolt with η = H is bounded by

V bolt H (s t , b t ) -ṼAt H (s t , b t ) ≤ (1 -γ H )η 2 (1 -γ)m . (7)
[Proof in App. A.3] Proof of Theorem 5.1. We start by the induced inequality (Lemma 5.2) with A t the policy generated by bolt at time t, and Ṽ a mixed value function using bolt's update when (s, a) / ∈ K. As Rmax = 1, the chain of inequalities is

V At (s t , b t ) ≥ V At H (s t , b t ) ≥ ṼAt H (s t , b t ) - 1 -γ H 1 -γ P r(A K ) ≥ V bolt H (s t , b t ) - η 2 (1 -γ H ) m(1 -γ) - 1 -γ H 1 -γ P r(A K ) ≥ V * H (s t , b t ) - η 2 (1 -γ H ) m(1 -γ) - 1 -γ H 1 -γ P r(A K ) ≥ V * (s t , b t ) - η 2 (1 -γ H ) m(1 -γ) - 1 -γ H 1 -γ P r(A K ) - γ H (1 -γ)
where the 3 rd step is due to Lemma 5.3 (accuracy) and the 4 th step to Lemma 4.1 (optimism). To simplify the analysis, let us assume that γ H

(1-γ) = 2 and fix m

= 4η 2 (1-γ) . If P r(A K ) > η 2 m = (1-γ) 4
, by the Hoeffding6 and union bounds we know that A K occurs no more than

O |S||A|m P r(A K ) log |S||A| δ = O |S||A|η 2 2 (1 -γ) 2 log |S||A| δ
time steps with probability 1 -δ. By neglecting logarithms we have the desired theorem. This bound is derived from the fact that, if A K occurs more than |S||A|m times, then all the stateaction pairs are known and we will never escape from K anymore. Here we are not considering the information already encoded in the prior, so this bound will be much more tight in practice.

For P r(A K ) ≤ η 2 m , we have that

V At (s t , b t ) ≥ V * (s t , b t ) - (1 -γ H ) 4 - (1 -γ H ) 4 - 2 ≥ V * (s t , b t ) - 4 - 4 - 2 = V * (s t , b t ) -
which verifies the proposed theorem.

Following [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], optimism can be ensured for beb with β ≥ 2H 2 , with

Õ |S||A|H 4 2 (1-γ) 2
non -close steps (see App. B.2), which is a worse result than bolt. Nevertheless, the bounds used in the proofs are loose enough to expect the optimism property to hold for much smaller values of β and η in practice.

Experiments

To illustrate the characteristics of bolt, we present here experimental results over a number of domains. For all the domains we have tried different parameters for bolt and beb, but also we have used an ε-greedy variant of exploit, where there is an ε probability of choosing a random action rather than following the policy of the expected model. However, for all the presented problems plain exploit (ε = 0.0) outperforms the ε-greedy variant.

Please recall that the theoretical values for parameters β and η-that ensure optimismdepend on the horizon H of the MDPs solved at each time step. In these experiments, instead of using this horizon we relied on asynchronous value iteration, stopping when V i+1 -V i ∞ < . Moreover, we reuse the final value function at time t as the initial value function at time t + 1 to speed computations. For solving these infinite MDPs we used γ = 0.95 and = 0.01, but be aware that the performance criterion used here is averaged undiscounted total rewards, following [START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF][START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF].

The Chain Problem

In the 5-state chain problem [START_REF] Malcolm | A Bayesian framework for reinforcement learning[END_REF][START_REF] Poupart | An analytic solution to discrete Bayesian reinforcement learning[END_REF], every state is connected to state s 1 by taking action b and every state s i is connected to the next state s i+1 with action a, except s 5 that is connected to itself. At each step, the agent may "slip" with probability p, performing the opposite action as intended. Staying in s 5 had a reward of 1.0 while coming back to s 1 had a reward of 0.2. All other rewards are 0. The priors used for these problems were Full (FDM), Tied, where the probability p is factored for all transitions, and Semi, where each action has an independent factored probability.

Algorithm

Tied Semi Full exploit (ε = 0) 366.1 354.9 230.2 beb (β = 1) 365.9 362.5 343.0 beb (β = 150) 366.5 297. Table 1 shows that beb outperforms other algorithms with a tuned up β value for the FDM prior as already shown by [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF]. However, for a large value of β, this performance decreases dramatically. bolt on the other hand produces results comparable with boss for a tuned parameter, but does not decrease too much for a large value of η. Indeed, this value corresponds to the theoretical bound that ensures optimism, η = H ≈ log( (1-γ))/ log(γ) ≈ 150. Unsurprisingly, the results of beb and bolt with informative priors are not much different than other techniques, because the problem degenerates into a easily solvable problem. Nevertheless, bolt achieves good results for a large η, in contrast to beb that fails to provide a competitive result for the Semi prior with large β.

This variability in the results depending on the parameters, rises the question of the sensitivity to parameter tuning. In a RL domain, one usually cannot tune the algorithm parameters for each problem, because the whole model of the problem is unknown. Therefore, a good RL algorithm must perform well for different problems without modifying its parameters.

Fig. 2 shows how beb and bolt behave for different parameters using a Full prior. In the low resolution analysis beb's performance decays very fast, while bolt also tends to decrease, but maintaining good results. We have also conducted experiments for other values of the slip probability p, the same pattern being amplified when p is near 0, i.e., worse decay for beb and almost constant bolt results, and obtaining almost identical behavior when p is near 0.5. In the high resolution results beb goes up and down near 1, while bolt maintains a similar behaviour as in the low resolution experiment.

Other Structured Problems

An other illustrative example is the Paint/Polish problem where the objective is to deliver several polished and painted objects without a scratch, using several stochastic actions with unknown probabilities. The full description of the problem can be found in [START_REF] Walsh | Exploring compact reinforcement-learning representations with linear regression[END_REF] the possible outcomes of each action are given to the agent, but the probabilities of each outcome are not. We have used a structured prior that encodes this information and the results are summarized in Fig. 3, using both high and low resolution analyses. We have also performed this experiment with an FDM prior, obtaining similar results as for the Chain problem. Unsurprisingly, using a structured prior provides better results than using FDMs. However, the high impact of being overoptimistic shown in Fig. 3, does not apply to FDMs, mainly because the learning phase is much shorter using a structured prior. Again, the decay of beb is much stronger than bolt, but in contrast to the Chain problem, the best parameter of bolt beats the best parameter of beb.

The last example is the Marble Maze problem7 [START_REF] Asmuth | A Bayesian sampling approach to exploration in reinforcement learning[END_REF] where we have explicitly encoded the 16 possible clusters in the prior, leading to little exploration requirements. exploit provides very good solutions for this problem, and bolt provides similar results with several different parameters. In contrast, for all the tested β parameters, beb behaves much worse than exploit. For example, for the best η = 2.0 bolt scores -0.445, while for the best β = 0.9 beb scores -2.127, while exploit scores -0.590.

In summary, it is hard to know a priori which algorithm will perform better for a specific problem with a specific prior and given certain parameters. However, bolt generalizes well (in theory and in practice) for a larger set of parameters, mainly because the optimism is bounded by the probability laws and not by a free parameter as in beb.

Conclusion

We have presented bolt, a novel and simple algorithm that uses an optimistic boost to the Bayes update, which is thus optimistic about the uncertainty rather than just in the face of uncertainty. We showed that bolt is strictly optimistic for certain η parameters, and used this result to prove that it is also PAC-BAMDP. The sample complexity bounds for bolt are tighter than for beb. Experiments show that bolt is more efficient than beb when using the theoretically derived parameters in the Chain problem, and in general that bolt seems more robust to parameter tuning. Future work includes using a dynamic η bonus for bolt, what should be particularly appropriate with finite horizons, and exploring general proofs to guarantee the PAC-BAMDP property for a broader family of priors than FDMs.

A Technical Proofs

A.1 Proof of Lemma 4.1

Proof. We will prove this lemma by finding an upper bound for the optimal Bayesian value function at iteration i. Then, by induction, we prove that the accumulated difference between bolt's value function and this upper bound is lower bounded by a positive quantity.

Let Q * H (s t , b t , a) be the optimal Bayesian state-action value function. We can upper bound this optimal Bayesian state-action value function at iteration i by

Q * i (s, b, a) = s θ s,a (s ) θ s,a (R(s, a, s ) + γV * i-1 (s , b )) ≤ max φ s θ t s,a (s ) + φ(s ) θ t s,a + φ (R(s, a, s ) + γV * i-1 (s , b )),
where b is a descendent of b t , meaning that b is a belief obtained by applying H -i Bayesian updates from b t , and where φ = θ s,a -θ t s,a . This inequality holds since there exists a vector φ such that θ s,a = θ t s,a + φ . Now, let us define

f (φ) = s θ t s,a (s ) + φ(s ) θ t s,a + φ g(s , s, a, b), with g(s , s, a, b) = R(s, a, s ) + γV * i-1 (s , b ).
Please note that f (φ) is a linear function because φ = C s,a is constant for a given state-action pair. Therefore, maximizing f (•) can be turned into to maximizing g(•, s, a, b) as follows: where the last step is due to all the elements in the fraction having positive values (i.e., H > C s,a ). This implies that V bolt i+1 (s, b t ) -V * i+1 (s, b) ≥ γ∆ i . So, by noticing that the base step is ∆ 0 = 0because V 0 (s, b) = V bolt (s, b t ) = 0-and applying this last equation repeatedly, we obtain the desired result by induction.

Q * i (s, b, a) ≤ max φ f (φ) = 1 θ t s,a + C s,
A.2 Proof of Lemma 5.2

Proof. This proof follows the same reasoning as Lemma 5 of [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], but generalized to be applied to a mixed value function, and also to the discounted reward case. Let p i Inria be a partial path generated by policy π, p i = s 0 , a 0 , s 1 , . . . , a i-1 , s i , P r(p i ) be the probability of obtaining that path given the prior belief b, and r(p i ) the reward for the last step of the partial path p i , i.e., (s i-1 , a i , s i ). Furthermore, let P r(p i ) and r(p i ) be respectively the product of transition probabilities along p i and the reward for the last step of the mixed value function Ṽ for a given path p i . Then,

Ṽπ H (s t , b t ) -V π H (s t , b t ) = H-1 i=1 γ i pi P r(p i )r(p i ) - H-1 i=1 γ i pi P r(p i )r(p i ) = H-1 i=1 γ i pi∈K P r(p i )r(p i ) -P r(p i )r(p i ) + pi / ∈K P r(p i )r(p i ) -P r(p i )r(p i ) = H-1 i=1 γ i pi / ∈K P r(p i )r(p i ) -P r(p t )r(p i ) ≤ H-1 i=1 γ i pi / ∈K P r(p i )r(p i ) ≤ (1 -γ H ) (1 -γ) Rmax P r(A K ),
where we divide the sum of paths in those that are always in K and those that escape from K.

If a path is in K, then the rewards and probabilities are equal, so they can be removed (third step), and in the last step we upper bound the difference by taking the maximum possible reward value, and the definition of P r(A K ).

A.3 Proof of Lemma 5.3

Proof. We prove this lemma by induction, where the inductive step i + 1 is based on the assumption that the difference between the two evaluations at iteration i is bounded by a maximum quantity ∆ i :

V bolt i (s, b t ) -ṼAt i (s, b) ≤ ∆ i . (10)
Now, we compute the maximum delta difference for i + 1, distinguishing between two cases. The first case is when (s, a) / ∈ K (with α = A t (s, b)), meaning that the probabilities and rewards for each term are the same. Formally,

∆ ( / ∈K) i+1 = V bolt i+1 (s, b t ) -ṼAt i+1 (s, b) = s T (s, α, s , b t ) (R(s, a, s )+ γV bolt i (s, b t ) -R(s, a, s ) -γ ṼAt i (s, b ) ≤ γ∆ i s T (s, α, s , b t ) = γ∆ i .
The second case is when (s, a) ∈ K, where the probabilities differ,

∆ (∈K) i+1 = V bolt i+1 (s, b t ) -ṼAt i+1 (s, b) = s T (s, α, s , b t )(R(s, a, s ) + γV bolt i (s, b t )) - s T (s, a, s , b)(R(s, a, s ) + γ ṼAt i (s, b )) ≤ γ∆ i + s T (s, α, s , b t ) -T (s, a, s , b) × R(s, a, s ) + γ ṼAt i (s, b ) = γ∆ i + s θ t s,a (s )+ηδ(σ,s ) θ t s,a +η - θs,a(s ) θs,a × R(s, a, s ) + γ ṼAt i (s, b ) ≤ γ∆ i + s ηδ(σ, s ) θ t s,a + η (R(s, a, s ) + γ ṼAt i (s, b )) ≤ γ∆ i + η 2 m .
Here, the third step is due to the definition of ∆ i . The fifth inequality holds because θ t s,a (s ) ≤ θ s,a (s ) and θ t s,a + H ≥ θ s,a . The last step is obtained because the maximum value of Ṽ is always less than H = η and that θ t s,a + H ≥ m because we are analyzing state-action pairs that are in K.

We can now safely define our maximum difference at iteration i + 1 as the worst case:

∆ i+1 = max(∆ ( / ∈K) i+1 , ∆ (

B BEB Description and Analysis

B.1 Bayesian Exploration Bonus

The Bayesian Exploration Bonus algorithm (beb) consists in solving at each time step t an MDP generated by the current expected model with a modified reward function depending on the current belief. Let R(s, a, s ) be the given reward function and b t the belief state at time t, then beb performs value iteration as follows:

V beb i (s, b t ) = max a s T (s, a, s , b t ) R(s, a, s , b t ) + γV beb i-1 (s , b t ) with R(s, a, s , b t ) = R(s, a, s ) + β 1 + θ s,a , where T = E M [µ | b t ] is the expected model of b t , i.e., T (s, a, s , b t ) = E[P r(s |s, a)|b t ] = θs,a(s )
θs,a , and β a parameter that controls the optimism of the algorithm. Please note that beb's value iteration neglects the evolution of b t , so at each time step t the algorithm solves an MDP with fixed transition and reward functions. If β ≥ 2H 2 , this algorithm is always optimistic compared to the optimal Bayesian value function for the undiscounted reward case, as stated in Lemma 4

Inria

The second case is when (s, a) ∈ K, where the probabilities and rewards differ,

∆ (∈K) i+1 = V beb i+1 (s, b t ) -ṼAt i+1 (s, b) = s T (s, a, s , b t )( R(s, a, s , b t ) + γV beb i (s, b t )) - s T (s, a, s , b)(R(s, a, s ) + γ ṼAt i (s, b )) ≤ s T (s, a, s , b t ) R(s, a, s , b t ) + γV beb i (s, b t ) -R(s, a, s ) -γ ṼAt i (s, b ) + s |T (s, a, s , b t ) -T (s, a, s , b)| × (R(s, a, s ) + γ ṼAt i (s, b )) ≤ s T (s, a, s , b t ) β 1 + θ t s,a + γ∆ i + (1 -γ i ) (1 -γ) s |T (s, a, s , b t ) -T (s, a, s , b)| ≤ β (1 + θ t s,a ) + γ∆ i + 2H(1 -γ i ) (1 -γ)(1 + θ t s,a ) ≤ 2β m + γ∆ i .
Here, the third step is due to the property x p(x)f (x) -q(x)g(x) ≤ x p(x)(f (x) -g(x)) +

x |p(x) -q(x)|g(x), which holds if all functions are positive. The next step is obtained by using the definitions of R and ∆ i in the left term, and considering the maximum possible value of R(s, a, s ) + γ ṼAt i (s, b ). The fifth step is obtained by Lemma 3 of [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], where the sum of the absolute differences s |T (s, a, s , b t ) -T (s, a, s , b)| ≤ 2H (1+ θ t s,a ) . The last step is due to the facts that (1 -γ i )/(1 -γ) ≤ H, and that 1 + θ t s,a ≥ m because we are analyzing state-action pairs that are in K.

We can now safely define our maximum difference at iteration i + 1 as the worst case:

∆ i+1 = max(∆ ( / ∈K) i+1 , ∆ (∈K) i+1 ) = 2β
m +γ∆ i . By applying this equation repeatedly with the base step ∆ 0 = 0, because V beb 0 (s, b t ) = ṼAt 0 (s, b) = 0, we obtain the desired result. With these lemmas, now we are ready to prove Theorem B.1, which shows that beb is PAC-BAMDP in the discounted infinite horizon case (without modifying the algorithm to stop monitoring beliefs as in [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF]).

Proof of Theorem B.1. Consider the induced inequality (Lemma 5.2) with A t the policy generated by beb at time t, and Ṽ a mixed value function using beb's update when (s, a) / ∈ K. As Inria beb's bonus is always decreasing, we can safely define Rmax = 2β (> 1 + β). Lemma B.2 is defined for a computing horizon H, so in order to use this result we first need to notice that a truncated summation is always smaller than the infinite summation. Starting from these facts, and assuming normalized rewards, we have that

V At (s t , b t ) ≥ V At H (s t , b t ) ≥ ṼAt H (s t , b t ) - 2β(1 -γ H ) (1 -γ) P r(A K ) ≥ V beb H (s t , b t ) - 2β(1 -γ H ) m(1 -γ) - 2β(1 -γ H ) (1 -γ) P r(A K ) ≥ V * H (s t , b t ) - 2β(1 -γ H ) m(1 -γ) - 2β(1 -γ H ) (1 -γ) P r(A K ) ≥ V * (s t , b t ) - 2β(1 -γ H ) m(1 -γ) - 2β(1 -γ H ) (1 -γ) P r(A K ) - γ H (1 -γ)
where the 3 rd step is due to Lemma B.2 (accuracy), the 4 th step to Lemma 4 of [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF] (optimism), and the last step to Lemma 2 of [START_REF] Kearns | Near-optimal reinforcement learning in polynomial time[END_REF]] (error bound between finite and infinite horizon computation) 8 .

Here, the error between V * (s t , b t ) and V At (s t , b t ) depends on H, β, m and γ, besides the probability P r(A K ). To simplify the analysis, let us assume that γ H

(1-γ) = 2 and fix m = 8β (1-γ) . Now we will consider two cases for P r(A K ). First suppose that P r(A K ) > 1 m = (1-γ) 8β , then by the Hoeffding and union bounds [START_REF] Valiant | A theory of the learnable[END_REF], this occurs in no more than

O |S||A|m P r(A K ) log |S||A| δ = O |S||A|β 2 2 (1 -γ) 2 log |S||A| δ
time steps with probability 1 -δ. By using the complexity notation that neglects logarithms we have the desired sample complexity of the theorem. This bound is derived from the fact that, if the event A K occurs more than |S||A|m times, then all the state-action pairs are known and we will never escape from K anymore. The second case is when P r(A K ) ≤ 1 m , where

V At (s t , b t ) ≥ V * (s t , b t ) - 2 (1 -γ H ) 8 - 2 (1 -γ H ) 8 - 2 ≥ V * (s t , b t ) - 4 - 4 - 2 = V * (s t , b t ) -
which verifies the proposed theorem.

8 Lemma 2 of [START_REF] Kearns | Near-optimal reinforcement learning in polynomial time[END_REF]] is presented for normal MDPs, but its applicability to BAMDPs is straightforward by using the same arguments.

RR n°7965

RESEARCH CENTRE NANCY -GRAND EST

  Low resolution analysis β, η ∈ [1, 100]High resolution analysis β, η ∈ [0.1, 10]

Figure 2 :

 2 Figure 2: Chain Problem. Averaged total reward over 300 trials for an horizon of 150, and for β and η parameters between 1 and 100, and between 0.1 and 10. As a reference, the value obtained by exploit is also plotted. All results are shown with a 95% confidence interval.

  . Here, Inria Low resolution Analysis β, η ∈ [1, 100] High resolution Analysis β, η ∈ [0.1, 10]

Figure 3 :

 3 Figure 3: Paint/Polish Problem. Averaged total reward over 300 trials for an horizon of 150, for several values of β and η using an structured prior. As a reference, the value obtained by exploit is also plotted. All results are shown with a 95% confidence interval.

  ∈K) i+1 ) = η 2 m + γ∆ i . By applying this equation repeatedly with ∆ 0 = 0, because V bolt 0 (s, b t ) = ṼAt 0 (s, b) = 0, we obtain the desired result.

  615 rue du Jardin Botanique CS20101 54603 Villers-lès-Nancy Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Table 1 :

 1 Chain Problem results for different priors. Averaged total reward over 500 trials for an horizon of 1000 with p = 0.2. The results with * come from previous publications.

		5 165.2
	bolt (η = 7)	367.9 367.0 289.6
	bolt (η = 150)	366.6 358.3 278.7
	beetle *	365.0 364.8 175.4
	boss *	365.7 365.1 300.3

  Let us now analyze the difference between the state-action value function of bolt,Q bolt H (s t , b t , a) = max σ Q bolt H (s t , b t , (a, σ)), and the optimal Bayesian value function V * H (s t , b t ). To prove the inductive step i + 1, let us assume that the difference between the value functions at iteration i is lower bounded by a positive quantity:0 ≤ ∆ i ≤ V bolt i (s, b t ) -V * i (s, b). Then, we can lower bound bolt's value at iteration i + 1 with η = H:

			a	s	θ t s,a (s )g(s , s, a, b)
				+ max φ	s	φ(s )g(s , s, a, b)
	≤	1 s,a + C s,a θ t	s	θ t s,a (s )g(s , s, a, b)	(8)
				+C s,a max σ	(g(σ, s, a, b))	.
	Q bolt i+1 (s, bt, a)
	= max σ	s	θ t s,a (s ) + Hδ(σ, s ) θ t s,a + H	(R(s, a, s ) + γV bolt i	(s , bt))
	= max σ	s	θ t s,a (s ) + Hδ(σ, s ) θ t s,a + H	(R(s, a, s ) + γ(∆i + V * i (s, b)))
	≥ γ∆i +	H maxσ(g(σ, s, a, b)) + s θ t s,a (s )g(s , s, a, b) θ t s,a + H	.	(9)
	Using Equations 8 and 9, we can show that the difference at iteration i + 1 can be bounded by
	Q bolt i+1 (s, bt, a) -Qi+1(s, b, a)
	≥ γ∆i +	H maxσ(g(σ, s, a, b)) + s θ t s,a (s )g(s , s, a, b) θ t s,a + H
	-	Cs,a maxσ(g(σ, s, a, b)) + s θ t s,a (s )g(s , s, a, b) θ t s,a + Cs,a
	≥ γ∆i
	+	(H -Cs,a) s θ t s,a (maxσ(g(σ, s, a, b)) -g(s , s, a, b)) θ t s,a + H
	≥ γ∆i,

RR n°7965

However, some-rectifiable-errors have been spotted in the proof of near-Bayesianness of beb in[START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF], as discussed with the authors.

We use a different notation for the Bayesian evaluation, V, to distinguish it from a normal MDP evaluation V .Inria

In case of equal values, actions are sampled uniformly.RR n°7965

To follow the proofs, please keep in mind that H is not the horizon of the problem (which is infinite in our analysis), but the computing horizon of the MDPs Inria

Even though the Hoeffding bound assumes that samples are independent, which is trivially not in MDPs, it upper bounds the case where samples are dependent. Recent results shows that tighter bounds can be achieve with a more elaborated analysis[START_REF] Szita | Model-based reinforcement learning with nearly tight exploration complexity bounds[END_REF].Inria

Averaged over 100 trials with H = 100.Inria

of [START_REF] Kolter | Near-Bayesian exploration in polynomial time[END_REF]. Moreover, we can easily extend this result to the discounted reward case, where the optimism is maintained for β ≥ 2H(1 -γ H )/(1 -γ). However, for simplicity we will choose for the analysis

B.2 Analysis of BEB

Theorem B.1 (beb is PAC-BAMDP). Let A t denote the policy followed by beb at time t with β = 2H 2 . Let also s t and b t be the corresponding state and belief at that time. Then, with probability at least 1 -δ, beb is -close to the optimal Bayesian policy

Let ṼAt H (s t , b t ) be the evaluation of the beb policy A t at time t using a mixed value function. In this case, R(s, a, s ) = R(s, a, s , b t ) the reward with bonus, and T (s, a, s ) = T (s, a, s , b t ) the expected transition model of b t .

Lemma B.2 (beb Mixed Bound

). The difference between the value obtained by beb and the value obtained by the mixed value function under the policy generated by beb, A t , with β = 2H 2 is bounded by

Proof. Following the same induction technique as for the proof of Lemma 5.3, let us assume that the difference between two evaluations at iteration i is bounded by a maximum quantity ∆ i . Again, we can divide the difference ∆ i+1 in two cases. The first case is when (s, a) / ∈ K, and, by the same arguments as in the proof of Lemma B.2, we have that