Scale-free adaptive planning for deterministic dynamics & discounted rewards
Peter L. Bartlett 1 Victor Gabillon 2 Jennifer Healey 3 Michal Valko 4
arXiv:2604.18312v1 [cs.LG] 20 Apr 2026
Abstract We address the problem of planning in an environment with deterministic dynamics and stochastic discounted rewards under a limited numerical budget where the ranges of both rewards and noise are unknown. We introduce PlaTγPOOS, an adaptive, robust, and efficient alternative to the OLOP (open-loop optimistic planning) algorithm. Whereas OLOP requires a priori knowledge of the ranges of both rewards and noise, PlaTγPOOS dynamically adapts its behavior to both. This allows PlaTγPOOS to be immune to two vulnerabilities of OLOP: failure when given underestimated ranges of noise and rewards and inefficiency when these are overestimated. PlaTγPOOS additionally adapts to the global smoothness of the value function. PlaTγPOOS acts in a provably more efficient manner vs. OLOP when OLOP is given an overestimated reward and show that in the case of no noise, PlaTγPOOS learns exponentially faster.
1. Introduction We consider the problem of planning in a general stochastic environment with deterministic dynamics and discounted rewards. Our goal is to recommend the best first action for an agent to take from a given state. We envision that the discount factor γ is known and that our learner has a limited allocation of n interactions to spend querying a generative model of the environment. The objective is to maximize the sum of discounted rewards of the best sequence of actions following from the recommended first action. This is equivalent to minimizing the simple regret. We introduce the algorithm PlaTγPOOS, Planning wiTh γ Plus an Online Optimization Strategy, as a robust and efficient scale-free alternative to the OLOP algorithm (open-loop optimistic planning, Bubeck & Munos, 2010; Leurent & Maillard, 2019) for this 1 University of California, Berkeley, USA 2 Noah’s Ark Lab, Huawei Technologies, London, UK 3 Adobe Research, San Jose, USA 4 SequeL team, INRIA Lille - Nord Europe, France. Correspondence to: Victor Gabillon <[email protected]>.
Proceedings of the 36 th International Conference on Machine Learning, Long Beach, California, PMLR 97, 2019. Copyright 2019 by the author(s).
setting. Our algorithm implements a scale-free function optimization strategy similar to SequOOL (Bartlett et al., 2019) rather than an upper-confidence-bound approach which allows us to efficiently adapt to the problem space without prior knowledge of the ranges of the noise or the rewards. Planning in a stochastic environment is an important setting often modeled by Markov decision processes (MDPs, Puterman, 1994; Bertsekas & Tsitsiklis, 1996). One approach to solving these settings is to find the optimal policy that maximizes the expected sum of rewards and then generate an action recommendation according to that optimal policy. Unfortunately, in most practical settings where we are limited by computational resources, finding this optimal policy is often not possible, especially when the state space becomes large. Therefore, instead of trying to estimate the optimal policy of the MDP, we focus only on finding the best first action given our budget. We evaluate the performance of the recommendation in terms of the simple regret, the difference in reward between choosing the optimal first action vs. choosing our recommended first action and then in both cases choosing an optimal sequence of actions following the first action. This metric is often used to evaluate planning strategies that optimize numeric budgets (Bubeck & Munos, 2010; Buşoniu & Munos, 2012; Grill et al., 2016), in contrast to the cumulative regret where we are penalized during the search for querying sub-optimal actions. Once the agent takes the first action and moves to the next state, our evaluation can be repeated with a new budget allocation and the following best first action can be recommended. This allows us to approximately follow an optimal policy, action by action, in an online way. Previously, there have been several strategies proposed on how to efficiently allocate a numeric budget to search for an optimal value in a stochastic space. Many of these have been successfully implemented using methods based on upper confidence bounds (UCBs) such as UCT (Upper Confidence Trees, Kocsis & Szepesvári, 2006). This approach has been proven to be very efficient in practice (Coulom, 2007; Gelly et al., 2006; Silver et al., 2016), however, UCT can badly misbehave on some problems (Coquelin & Munos, 2007) and more theoretically sound approaches have been proposed (Hren & Munos, 2008; Bubeck & Munos, 2010; Buşoniu & Munos, 2012; Feldman & Domshlak, 2014; Szörényi et al., 2014; Kaufmann & Koolen, 2017; Shah et al., 2019). Some of
Scale-free adaptive planning for deterministic dynamics & discounted rewards
these methods are connected to the ones from function optimization (Bubeck et al., 2011; Munos, 2011; Valko et al., 2013) as shown by Munos (2014), however, one key difference is that in planning, as opposed to function optimization, the structure of the reward is a discounted reward, specifically a sum of rewards discounted by factor γ. This reward structure influences the behavior of the optimizers (Bubeck & Munos, 2010), in particular, the discount factor brings smoothness to the value function which in turn makes it easier to optimize. PlaTγPOOS exploits the effect of the discount factor to efficiently manage an adaptive planning strategy in the face of unknown ranges of noise and rewards. This adaptive strategy of PlaTγPOOS makes it more robust and efficient in practice than other planning strategies. For example, even though they are theoretically sound, the empirical performance of UCB-based approaches depends on the careful tuning of the upper confidence bound. If the upper confidence bound is too large then the UCB-based learner plays very conservatively by overestimating suboptimal options for many rounds. Moreover, these UCBs might depend on instance parameters that are simply not known such as the range of the rewards and the range of the noise. We build on the function optimization approach of Bartlett et al. (2019) that does not use UCBs and obtains improved results over the state-of-the-art by adapting to the problem difficulty with a scale-free approach. PlaTγPOOS adapts this scale-free optimization to planning. This scalefree property becomes a desired feature as machine learning gets closer to applications, whether it is online (Ross et al., 2013; Orabona & Pál, 2018) or deep learning (Orabona & Tommasi, 2017), since many parameters are never known. In terms of planning strategy, the PlaTγPOOS algorithm is an adaptive, robust, and efficient alternative to OLOP. Whereas OLOP requires the knowledge of where the ranges of both rewards and noise, PlaTγPOOS dynamically adapts its behavior to the both ranges, as well as some potential additional global smoothness of the value function. Our algorithm’s ability to adapt allows it to avoid failure in cases where the ranges of noise and rewards are underestimated and to act more efficiently in cases where they are overestimated. PlaTγPOOS recovers the results of OLOP while allowing improvements in various classes of problems. Our contributions We show that PlaTγPOOS • adapts its behavior to an unknown range of rewards, • requires no apriori assumptions or knowledge on noise, • empirically learns much faster than UCB approaches, • gets the fast rate of deterministic planning in low noise for all regime; in particular, it learns exponentially faster than OLOP when there happens to be no noise, • adapts also the global smoothness ρ and ν beyond the base smoothness provided by γ. We additionally address a realistic constraint where the
agent can only reset to the original state and not to any state it wishes. Our results hold for MDPs with deterministic dynamics and can equally be applied to open loop planning problems (as discussed by Munos 2014) where we search for the best sequence of actions, ignoring the actual states that are reached after each action (Bubeck & Munos, 2010). Related algorithms, where the objective is to find the value of the state rather than to identify the best action, include TrailBlazer (Grill et al., 2016) and StOP (Szörényi et al., 2014). A key difference is that these algorithms are fixed confidence and output a value using a small number of samples given an accuracy/probability, whereas our algorithm does exploration under a fixed budget of samples and guarantees how good the found action is. Even for simple multi-arm bandits, these two problems have different complexity (Carpentier & Locatelli, 2016) and can only be equivalent under unrealistic side knowledge (Gabillon et al., 2012). These related algorithms are also impractical for our setting. TrailBlazer uses confidence bounds that are humongous and StOP takes exponential time. Similar to OLOP, both also need to know noise and reward ranges.
2. Background We model our problem with an MDP with state space X, action space A and dynamics such that taking the chosen action at at time t deterministically transitions the system from xt ∈ X to state xt+1 ≜ f (xt , at ) generating a reward rt ≜ r(xt , at ) + εt , with εt being the noise. We consider: deterministic rewards The evaluations are noiseless, that is for all t, εt ≜ 0 and rt ≜ r(xt , at ). stochastic rewards The evaluations are perturbed by a noise of range b ∈ R+ : At any round, εt is a random variable, independent from noise at previous rounds, E [rt | xt ] ≜ r(xt , at ) and |rt − r(xt , at )| ≤ b. (1) We assume that all rewards lie in the interval [0, Rmax ] and while the state space may be large and possibly infinite, that the action space is finite, with K available actions. We treat an infinite time-horizon problem with discounted rewards where the discount factor (0 ≤ γ < 1) is known. For any possible policy π : X → A, we define the value V π : X → R associated to π as P function π t V (x) ≜ γ r(xt , π(xt )), where xt is the state of the system at time t when starting from x (i.e., x0 ≜ x) and following policy π. In the next definition, we also define the Q-value function Qπ : X × A → R associated to policy π, for each state-action pair (x, a), as the value of playing action a in state x and the following π thereafter. Definition 1. The Q-value function Qπ of policy π is Qπ (x, a) ≜ r(x, a) + γV π (f (x, a)).
Scale-free adaptive planning for deterministic dynamics & discounted rewards
Notice that V π (x) = Qπ (x, π(x)). We define the optimal value function, and Q-value function respectively, as V ⋆ (x) ≜ supπ V π (x) and Q⋆ (x, a) ≜ supπ Qπ (x, a), which corresponds to playing a first and optimally after. From the dynamic programming, we have the Bellman equations (Bertsekas & Tsitsiklis, 1996; Puterman, 1994), V ⋆ (x) = max r(x, a) + γV ⋆ (f (x, a)), a∈A
Q⋆ (x, a) = r(x, a) + γ max Q⋆ (f (x, a), b). b∈A
Let [a : c] ≜ {a, a + 1, . . . , c} with a, c ∈ N, a ≤ c, and [a] ≜ [1 : a]. Let logd be the logarithm in base d, d ∈ R and log without a subscript be the natural logarithm. 2.1. Optimistic planning under finite numerical budget We assume that we have a generative model of f and r that generates simulated transitions and rewards. We want to make the best possible use of this model in order to recommend a best next action a(n) such that the sum of the rewards resulting from playing a(n) and then optimally afterwards is as close as possible to playing optimally from the beginning. For that purpose, we define the performance loss that we aim to minimize rn as rn ≜ max Q⋆ (x, a) − Q⋆ (x, a (n)) . a∈A
2.2. The planning tree For a given initial state x, consider the (infinite) planning tree defined by all possible sequences of actions (thus all possible reachable states starting from x). Let A∞ be the set of infinite sequences (a0 , a1 , a2 , . . .) where at ∈ A. The branching factor of this tree is the number of actions K ≜ |A|. Since the dynamics are deterministic, to each finite sequence a ∈ Ad of length d we assign a state that is reachable starting from x by following this sequence of d actions. Using standard notation for alphabets, we write A0 ≜ {∅} and A• for the set of finite sequences. For a ∈ A• , we let h(a) be the length of a, and aAh ≜ {aa′ , a′ ∈ Ah }, where aa′ denotes the sequence a followed by a′ . We identify the set of finite sequences a ∈ A• with the set of nodes of the tree. With h′ ≤ h and a ∈ Ah , we denote a[h′ ] the sequence of action composed of the h′ first actions from a, i.e., {a0 , . . . , ah′ −1 }. We fix a[0] ≜ ∅. The value v(a) of an infinite sequence a ∈ A∞ is the discounted sum of rewards along the trajectory starting from the initial state x and defined by the choice of this sequence of actions, X v(a) ≜ γ t r(xt , at ), where x0 = x; xt+1 ≜ f (xt , at )· t≥0
Now, for any finite sequence a ∈ A• , or node, we define the value v(a) ≜ supa′ ∈A∞ v(aa′ ). We write v ⋆ ≜ v(∅) = supa∈A∞ v(a) for the optimal value at the initial state which
is the root of the tree, v ⋆ = V ⋆ (x). We denote the set of optimal infinite sequence of action as A⋆ which contains any a ∈ A∞ such that v(a) = v ⋆ . We note the set of optimal finite sequence of actions of depth h as A⋆,h which contains any a ∈ Ah such that v(a) = v ⋆ . We also define the u- and b-values for the lower- and upper- bounds on v(a) as h(a)−1
u(a) ≜
X
γ t r(xt , at ), and b(a) ≜ u(a) +
t=0
γ h(a) Rmax · 1−γ
Indeed, since all rewards are in [0, Rmax ], we trivially have that u(a) ≤ v(a) ≤ b(a). At any finite time t an algorithm has opened a set of nodes, which defines the expanded tree Tt . We say the learner opens (or expands) a node a with m evaluations if uses the generative model f and r to generate m transitions and rewards for the K children nodes aA. In the deterministic reward feedback, m = 1. The bounds reported in this paper are in terms of the total number of openings n, instead of evaluations. The number of function evaluations is upper bounded by Kn. Tx,a denotes the total number of evaluations allocated to action a ∈ A in state x. We define, especially for the noisy case, the estimated value of the reward rb(x, a) of action a ∈ A in state x. Given the Tx,a evaluations r1 , . . . , rTx,a , we PTx,a 1 let rb(x, a) ≜ Tx,a s=1 rs be the empirical average of rewards obtained at when performing action action a ∈ A in state x. To ease notation, for a ∈ Am and h ≤ m, we write Ta ≜ E[Txh(a)−1 ,ah(a)−1 |xt+1 ∼ P (·|xt , at ), x0 = x] for the number of pulls to the last action in a. Similarly, rbh (a) ≜ E[b r(xh , ah )|xt+1 ∼ P (·|xt , at ), x0 = x] and rh (a) ≜ E[r(xh , ah )|xt+1 ∼ P (·|xt , at ), x0 = x]. In the case of deterministic dynamics, xh is such that xt+1 ∼ P (·|xt , at ) and x0 ≜ x is a fixed state from which we can sample from if we have a full access to the generative model. Hence, for a finite sequence a ∈ A• or a node, h(a)−1
u b(a) ≜
X t=0
h(a)−1
γ t rb(xt , at ) =
X
γ t rbt (a).
t=0
We assume the existence of at least one a⋆ ∈ A∞ for which V ⋆ (x) = supa∈A∞ v(a) and define a smoothness for v. Proposition 1. There exists ν ∈ (0, Rmax / (1 − γ)] and ρ ∈ (0, γ] such that ∀h ≥ 0, ∀a ∈ Ah , u(a) ≥ v(a) − νρh . Note that this holds automatically for ν = Rmax / (1 − γ) and ρ = γ. For problems with an extra regularity this may also hold for some ν < Rmax / (1 − γ) and ρ < γ. Note that our results automatically adapt to ρ without knowing its value. Moreover, note that while having a smoothness ρ means having rewards diminishing geometrically with depth with a ratio of ρ, the constant ν is linked to the scale of variation of the V which can often be realistically smaller than ν < Rmax / (1 − γ). We now define a measure of the quantity of near-optimal sequences for the smoothness ν, ρ.
Scale-free adaptive planning for deterministic dynamics & discounted rewards
Definition 2. For any ν > 0 and ρ ∈ (0, 1), the branching factor κv (ν, ρ) with associated constant C, is defined as κv (ν, ρ) ≜ inf κ ≥ 1 : ∃C > 1, ∀h ≥ 0, Nhv (3νρh ) ≤ Cκh , where Nhv (ε) is the number of nodes a ∈ Ah of depth h such that v(a) ≥ v ⋆ − ε. We also define a related quantity but different from κv (ν, ρ). In particular, we define κu (ν, ρ) that uses Nhu (ε) instead of Nhv (ε) where Nhu (ε) is the number of nodes a ∈ Ah of depth h such that u(a) ≥ v ⋆ − ε. Our results use the new quantity κu (ν, ρ), recover the previous results using κv (ν, γ) in the method of Bubeck & Munos (2010) and go beyond them. Indeed, theirs are only formulated for ρ = γ while we prove the following claim in Appendix A. Proposition 2. κu (ν/2, γ) ≤ κv (ν, γ) ≤ κu (2ν, γ).
3. Optimization vs. planning Our PlaTγPOOS approach is a very close sibling to the flat optimization algorithm, StroquOOL (Bartlett et al., 2019), however, we explain how the structure of the planning setting and the discount factor γ shaped our approach. The optimal application of an optimization algorithm to the planning setting is not straightforward as discussed by Bubeck & Munos (2010). In their Section 2.2, Bubeck & Munos (2010) show that optimization can be applied to the planning problem either in a naı̈ve way or a good way. The authors take as an example the uniform planning problem. The naı̈ve and good strategies are evaluated by comparing the uncertainty |u(a) − u b(a)| of their estimates u b(a). Both strategies collect rewards identically, evaluating u(a) for all the K H nodes a ∈ AH at a fixed depth H ≜ h(a) by allocating one episode (of length H) for each a and receiving rh,a , 1 ≤ h ≤ H. In the naı̈ve version, for all sequences a, the estimation of u(a) uses only the H samples collected in Ph(a)−1 the one episode related to a. Here u b(a) ≜ h=0 γ t rh,a and Ta[h] = 1. In contrast, the good planning strategy reuses estimates. For two distinct sequences a and a′ , the good strategy reuses any sample of rh,a it gets for the estimation of both u(a) and u(a′ ) if a[h] = a′[h] . In Ph(a)−1 P 1 ′ this case, u b(a) ≜ h=0 γ t K H−h a′ :a[h] =a′ rh,a and [h]
Ta[h] = K H−h . This comparison is used to demonstrate the advantage of the use of the cross-sequence information to concentrate the estimate of the mean reward associated with each action more efficiently. It is by using this type of cross-sequence information that OLOP is able to obtain a reduced regret over a naı̈ve application of HOO for optimization (Bubeck et al., 2011) to the planning problem. The previous discussion on cross-sequence information is tied to the case of uniform exploration strategies. Good uniform strategies guarantee Ta[h] = K Hu −h by exploring
Input: n, A Initialization: open t0,1 ; hmax ← n/log(n) For h = 1 to hmax open ⌊hmax /h⌋ nodes ah,i of depth h with largest values u(ah,i ) Output x(n) ← arg max u(ah,i ) ah,i :∈T
Figure 1. Algorithm for free planning with no reset condition
until a reasonably shallow depth Hu but sampling all K Hu nodes and sharing cross sequence information. In the case of OLOP, HOO, or, particularly StroquOOL, only a subset S of size |S| ≪ K Hu of the most promising nodes are explored but at a deeper depth Hs ≫ Hu . Therefore, obtaining a lower bound on the number of sequence of actions at depth Hs that contains a for a given sub-sequence of actions a at depth h < Hs is complex in general. Actually one can design a problem with two actions that would drastically limit the amount of cross-sequence information for the optimal sequence of actions a⋆ in StroquOOL. As a result, applying StroquOOL with information sharing may not be enough and we chose to algorithmically ensure hat a node at depth h + 1 will be pulled γ 2 times less than a node at depth h. Indeed, using Chernoff-Hoeffding inequalities, Ph(a)−1 p we have |u(a) − u b(a)| ≤ h=0 γ h / Ta[h] . However, PlaTγPOOS, through some simple reparametrization, remains very close to StroquOOL and we leave as an open question whether equivalent theoretical guarantees could be proved directly for StroquOOL applied to planning.
4. Deterministic dynamics and rewards In this section, we consider a simpler case of deterministic rewards in order to introduce our new ideas. The evaluations are noiseless, that is ∀t, εt ≜ 0 and rt ≜ r(xt , at ). In Figure 1, we provide the SequOOL (Bartlett et al., 2019) algorithm applied to planning. In this case, it is straightforward to follow the analysis of SequOOL in order to obtain the same rates of simple regret as the state of the art algorithm OPD for the doubly deterministic case (Hren & Munos, 2008; Munos, 2014), up to logarithmic factors; and get the result1 of Theorem 1. This direct usage was already discussed by Munos (2014, Section 5.1). Using SequOOL for planning already permits to have an algorithm that does not use the parameter Rmax and that adapts to extra smoothness in the value function ν, ρ as discussed Section 2. Note that to obtain similar adaptations to Rmax , ν, and ρ, we could have already used SOO (Munos, 2014). However, SOO does not come with optimal simple regret (Bartlett et al., 2019). 1
log(n) is the n-th harmonic number
Scale-free adaptive planning for deterministic dynamics & discounted rewards
Input: n, A Initialization: open t0,1 ; hmax ←
j
n log n
Input: n, A Initialization: open the j k root node ∅, hmax times n hmax ← 2(log n+1)2 , pmax ← ⌊log2 (hmax )⌋
k
For h = 1 to hmax open hmax /h2 nodes ah,i of depth h with largest values u(ah,i ) Output x(n) ← arg max u(ah,i )
2
For h = 1 to hmax ◀ exploration ▶ For p = log2 (hmax / h2 γ 2h ) down j to 0 k p 2h hmax open h2 γ times the at most h⌈h2 p γ 2h ⌉
ah,i :∈T
non-opened nodes ah,i ∈ Ah with highest values u b(ah,i ) and given Tah,i ≥ (h − 1)2p γ 2(h−1)
Figure 2. Algorithm for constraint planning (restart)
Theorem 1. For any planning problem with associated (ν, ρ), and branching factor κ ≜ κu (ν, ρ), the simple regret of SequOOL is after n rounds bounded as follows. 1
j
• If κ = 1, then rn ≤ νρ C
n log n
• If κ > 1, then rn = O ν
k
.
log κ C
j
n log n
1/ρ k− log log κ
! .
On the reset condition In practice, physical constraints can force the exploration to interact with the unknown environment under a reset condition. This means that there exists a starting state x and a trajectory needs to start from this state and following a given policy. Therefore, if we wish to collect a sample from an arbitrary state x′ after a reset, we must first reach that state from the starting state x. SequOOL is a strategy that explores the MDP deeper and deeper from an initial starting state x. The original SequOOL strategy did not consider any reset condition, so to make a comparable analysis we will say that to ‘open’ a node a you first need to reach a at a budget cost of h(a) which is equal to the depth of a. This additional cost has the consequence that SequOOL with reset will not be able to explore as deeply as without. A naı̈ve extension is shown in Figure 2. Under a total limited budget of n, the number of nodes now open at depth h is O(n/h2 ) instead √ of O(n/h) and the maximal depth is now of order of n instead of n. However, this does not influence the simple regret when κ > 1 by more than numerical constants as shown in Theorem 2. When κ > 1, the exponentially diminishing simple regret remains √ but is changed from ρn to ρ n . Theorem 2. For a planning problem with associated (ν, ρ), and branching factor κ ≜ κu (ν, ρ), after n rounds, the simple regret of SequOOL with condition verifies: r reset j k • If κ = 1, then rn ≤ νρ
1 C
• If κ > 1, then rn ≤ O ν
n log n
log κ C
. j
n log n
1/ρ k− log log κ
! .
5. Deterministic dynamics, stochastic rewards We now describe the PlaTγPOOS algorithm detailed in Figure 3. In the presence of noise, it is natural to evaluate the
For p ∈ [0 : pmax ] ◀ cross-validation ▶ 2t evaluate (t + 1)γ hmax (1 − γ 2 )2 times the actions at round t, apt , of the candidates: ap ← arg max u b(a) a∈A• :∀t∈[2:h(a)],Ta[t] ≥⌈(t−1)2p γ 2(t−1) ⌉ Output an ← arg max u b(ap ) {ap ,p∈[0:pmax ]}
Figure 3. The PlaTγPOOS algorithm
cells multiple times, not just one time as in the deterministic case. The amount of times a cell should be evaluated to differentiate its value from the optimal value of the function depends on the gap between these two values as well as the range of noise. As we do not want to make any assumptions on knowing these quantities, our algorithm tries to be robust to any potential values by not making a fixed choice on the number of evaluations. Intuitively, we do this following a path similar to StroquOOL (Bartlett et al., 2019) by using a modified version of SequOOL, denoted SequOOL(m), that allows us to evaluate cells m times, whereas for SequOOL, m = 1. Evaluating cells more times (m large) leads to a better quality of the mean estimates in each cell, however, as a trade-off, it uses more evaluations per depth. This would normally limit us from exploring deep depths of the partition, however, PlaTγPOOS takes advantage of the knowledge of γ which gives less weight to reward collected deeper in the tree. In order to obtain the concentration results for a node a on u b(a) − u(a) in Lemma 2, PlaTγPOOS uses a Chernoff-Hoeffding qPresult that gives with high probh(a)−1 2h ability, u b(a) − u(a) ≤ γ /Ta[h] and balances h=0 the range of confidence intervals at different depths. Therefore, PlaTγPOOS tends to pull less depth as the with deeper number of pulls for a fixed m is hmγ 2h where the additional h factor ensures that the sum of confidence interval until depth h is bounded for any h. PlaTγPOOS then implicitly performs log n instances of SequOOL(m) each with a number of evaluations of m = 2p , where p ∈ [0 : log n]. In Figure 3, remember that ‘opening’ a node means ‘evaluating’ its children actions. The algorithm opens nodes by sequentially diving them deeper and deeper from the root
Scale-free adaptive planning for deterministic dynamics & discounted rewards
node h = 0 to a maximal depth of hmax . At depth h, we allocate, in an almost fashion, different decreasing number of evaluations h2p γ 2h to the nodes with highest value of that depth, with p starting at ⌊log2 (hmax /h)⌋ down to 0. The best node that has been evaluated at least O(hmax /h) times is opened with O(hmax /h) evaluations, the two next best cells that have been evaluated at least O(hmax /(2h) times are opened with O(hmax /(2h)) evaluations, the four next best cells that have been evaluated at least O(hmax /(4h)) times are opened with O(hmax /(4h)) evaluations and so on, until some O(hmax /h) next best cells that have been evaluated at least once are opened with one evaluation. More precisely, given, p and h, we open, with h2p γ 2h evaluations, the hmax /(h h2p γ 2h ) nonpreviously-opened nodes ah,i ∈ Ah with highest values u b(ah,i ) and given that Tah,i ≥ (h − 1)2p γ 2(h−1) . The maximum number of evaluations of any node is 2pmax , with 2pmax = O(hmax ) as pmax ≜ ⌊log2 (hmax )⌋. For each p ∈ [0 : pmax ], the candidate output ap is the node a with the highest estimated value such that all actions leading to that node have been evaluated in the following way ∀t ∈ [2 : h(a)], Ta[t] ≥ (t − 1)2p γ 2(t−1) . We set hmax ≜ n/(2(log2 n + 1)2 ) . 5.1. Analysis of PlaTγPOOS ⊥h,p is the depth of the deepest opened node, a with at least h2p γ h evaluations such that there is a a⋆ ∈ A⋆ with a⋆ ≜ ab, with b ∈ A∞ , at the end of the opening of depth h. Lemma 1. For any planning problem with associated (ν, ρ) as in Property 1), on event ξ defined in Appendix C, for any depth h ∈ [hmax ] , for any p ∈ [0 : log2 (hmax /(h2 γ 2h )) ], we have p ⊥h,p = h if (1) and (2) simultaneously hold: (1) b log(4n/δ)/2p+1 ≤ νρh (2) We distinguish cases and express the condition in each: Case 1) h2p γ 2h ≤ 1 : hmax hmax = ≥ Cκ(ν, ρ)h h h ⌈h2p γ 2h ⌉ ′ hmax and for all h′ ∈ [h], ′2 p+1 2h′ ≥ Cκ(ν, ρ)h h 2 γ Case 2) h2p γ 2h ≥ 1 : hmax Case 2.1) γ 2 κu ≥ 1 : 2 p+1 2h ≥ Cκ(ν, ρ)h h 2 γ hmax Case 2.2) γ 2 κu ≤ 1 : 2 p+1 ≥ C h 2 Lemma 1 gives two conditions so that the cell containing a a⋆ ∈ A⋆ is opened at depth h. This holds if (1) PlaTγPOOS opens, with h2p γ 2h evaluations, more cells at depth h than the number of near-optimal cells at depth h (hmax / h2 2p γ 2h ≥ Cκ(ν, ρ)h if γ 2 κu ≥ 1 and hmax /h2p ≥ C if γ 2 κu ≤ 1) and (2) the h2p γ 2h evalu-
ations are sufficient to discriminate the empirical average of near-optimal p cells from the empirical average of suboptimal cells (b log(4n/δ)/2p+1 ≤ νρh ). To state the next theorems, we introduce e h, e h1 , and e h2 three positive real numbers satisfying respectively the equations: e e δ,Rmax 2e hmax ν 2 ρ2h1 / e h1 b2 gn,b γ h1 = Cκh1 and e δ,Rmax hmax ν 2 ρ2h2 / e h2 b2 gn,b = C, where e h1 = log(γ 21κ/ρ2 ) log 1 e h2 = log(1/ρ 2 ) log 2
n1 log n1
n2 log n2
2
+ o(1) and
+ o(1) with
2
2
2
log(γ κ/ρ ) , max log(1/ρ ) , n1 ≜ ν hmax n2 ≜ ν hCb 2 g δ,Rmax Cb2 g δ,Rmax n,b
n,b
δ,Rmax where gn,b ≜ pmax log(Rmax n3/2 /b(1 − δ)). e h is defined similarly in Equation 5 in Appendix D. The quantities e h1 and e h2 give the respective depths of deepest cell opened by PlaTγPOOS that contains a a⋆ with high probability in the cases γ 2 κ ≥ 1 and γ 2 κ ≤ 1. Additionally, e h1 and e h2 also let us characterize for which regime of the noise range b we recover results similar to the loss of the deterministic case. Discriminating on the noise regimes, we now state two of our results, Theorem 3 for a high noise and Theorem 4 for a low one. A more exhaustive list of results is in the Appendix D or in the Table 1.
Theorem 3. High-noise regime If the noise b is high enough to verify both high-noise conditions as defined in the caption of Table 1, then after n rounds, for any problem with associated (ν, ρ), and branching factor κ ≜ κu (ν, ρ), the simple regret of PlaTγPOOS obeys 1 e n2 − 2 if γ 2 κ ≤ 1, O b Ern = log(1/ρ) n − log(γ 2 κ/ρ2 ) e if γ 2 κ > 1. O b2 The proofs are in appendix D. They are quite technical but they are simply based on checking the conditions of Lemma 1 under different b, ρ, γ, κ regimes. Theorem 4. Low-noise regime If the noise b is low enough to verify both high-noise conditions as defined in the caption of Table 1, then after n rounds, for any problem with associated (ν, ρ), and branching factor κ ≜ κu (ν, ρ), the simple regret of PlaTγPOOS obeys
Ern =
e (νρn ) O e ν O
log(1/ρ) n − log(κ)
b2
if κ = 1, if κ > 1.
Scale-free adaptive planning for deterministic dynamics & discounted rewards
γ2κ ≤ 1 High noise (ii) mν,γ
High noise (i)
1 n −2 b2 log(1/ρ)
Low noise (i)
mν,γ
n − log(κ) b2
γ2κ ≥ 1
Low noise (ii) √
νρ n
High noise (iii) mν,γ
n b2
mν,γ
n − log(κ) b2
κ = 1 : νρn κ>1:ν
n b2
log(1/ρ) − log(κ)
Low noise (iii)
log(1/ρ) − log(γ 2 κ/ρ2 )
log(1/ρ)
ν
n − log(κ) b2
ν
n − log(κ) b2
log(1/ρ)
log(1/ρ)
Table 1. Rates of the our upper bounds on the simple regret of PlaTγPOOS for various classes. The condition on noise (i) is whether the e e e δ,Rmax δ,Rmax noise b verifies ν 2 ρ2h /(γ 2h e hb2 gn,b ) ≤ 1 The condition on noise (ii) is whether ν 2 ρ2h2 /(b2 gn,b ) ≤ 1. The condition on noise δ,Rmax (iii) is whether ν 2 ρ2h1 /(b2 gn,b ) ≤ 1. Moreover, mν,γ ≜ max(1/1 − γ 2 , ν). e
Worst-case comparison with OLOP when b is large and known In Table 1, we give our results for various classes of problems depending on the whether γ 2 κ ≥ 1, whether κ = 1 or κ > 1, and several conditions for the range of the noise b. The results for OLOP were distinguishing the results based on γ 2 κ being greater or smaller than 1. For these two cases, we recover the same rate in term of n for the simple regret, as displayed in Table 1 with a grey background color, for instance taking b = 1 like in OLOP and having ρ = γ. However, we provide more specific treatment for sub-cases with associated improvements that we list and detail next. Adaptation to the range of the noise b without a prior knowledge Our analysis shows that PlaTγPOOS adapts favorably to the unknown range of noise. Already, in the standard cases discussed above, where the noise is large, our bound already adapts to the amount of noise as it scales with n/b2 . OLOP requires an estimate eb of b and has a regret scaling with n/eb2 which is problematic in case of a wrong estimate eb ≫ b. Moreover, we give technical conditions on the range of noise that shows when PlaTγPOOS gets improved rates. When γ 2 κ ≥ 1, OLOP was already obtaining rates that were the same as the rates of deterministic reward case. Therefore, beyond the n/b2 improvement and the adaptation to extra smoothness that will be discussed latter, no more rate improvement should be expected. In the case γ 2 κ ≤ 1, the improvement are even more striking. When the√noise is very low, then contrary to the OLOP rate of O(1/ n), we obtain the deterministic rate of OPD (Hren & Munos, 2008; Munos, 2014) which is either n− log(1/ρ)/ log κ or ρn . These improved rates could not be obtained by OLOP. Indeed, OLOP relies on upper confidence bound (UCB) that uses a range of the noise eb as input, u(a) = O u b(a) +
h(a)−1
X h=0
s h(a) 1 R γ max · γ heb + Ta[a] 1−γ
This works if eb = b. However, the true b is unknown. If b = 0, using any eb > 0 will not result in an improved rate. Adaptation to additional smoothness ν and ρ beyond γ As defined in Section 2, we aim to adapt to the true smoothness ν, ρ of V which can go beyond γ. We show that PlaTγPOOS is able to take advantage of ν, ρ in a large portion of cases. In most cases, the rate γ in OLOP is replaced by ρ in PlaTγPOOS. In the case where γ 2 κ ≥ 1 we have log(1/γ)
rOLOP = O(n− log(κ) ) ≤ O(n
log(1/ρ)
− log(γ 2 κ/ρ2 )
) = rPlaTγPOOS .
Adaptation to the deterministic case and κ = 1 PlaTγPOOS adapts to the branching factor κ of the problem that under low noise conditions, leads to an √ exponentially decreasing simple regret rnPlaTγPOOS = O(νρ n ). This is a light-years improvement over OLOP for these conditions, as OLOP’s regret is at best rnPlaTγPOOS = O(n−1/2 ). This result is possible because PlaTγPOOS explores much deeper than OLOP, as its maximal depth is of order n. Actually, in most scenarios, the actual larger depth explored will be of order √ n due to sampling limitations. On the other hand, OLOP can only go log n deep. Moreover, κ = 1 is a common case in planning. Indeed, as discussed by Bubeck & Munos (2010), κ = 1 is equivalent to having near-optimal dimension d = 0 in an optimization task (Munos, 2014) which is a common value as shown by Valko et al. (2013). Therefore, we expect the case when γκ2 ≤ 1, that is, where we get the most significant improvement other OLOP, to be the most common in practice. The reset condition As discussed in Section 4, in the stochastic reward case, the effect of the reset condition affects, PlaTγPOOS as follows. First, all polynomial rates stay the same. Next, only the exponential rates √ change. A ρn rate√ without the condition becomes a ρ n with it. 1/3 Next, a ρ n rate becomes a ρn one.
Scale-free adaptive planning for deterministic dynamics & discounted rewards 100 80
60
60
40 20 0
2000
3000
4000
80
40 20
PlaTγPOOS OLOP
1000
100 PlaTγPOOS OLOP
return
80
return
return
100
0
5000
1000
2000
3000
4000
0
5000
20
60
OLOP, b̃ = 40
40
4000
0
5000
5000
OLOP, R̃max = 120 OLOP, R̃max = 130
80
OLOP, R̃max = 140 OLOP, R̃max = 150
60 40
20 3000
4000
OLOP, R̃max = 110
100
OLOP, b̃ = 10
return
40
3000
120
80
return
return
60
2000
OLOP, b̃ = 5 OLOP, b̃ = 20
2000
1000
budget n
100 PlaTγPOOS OLOP
1000
40
budget n
100
0
60
20
budget n
80
PlaTγPOOS OLOP
20 1000
2000
budget n
3000
budget n
4000
5000
0
1000
2000
3000
4000
5000
budget n
Figure 4. Top and bottom left: Average cumulative discounted return collected by OLOP and PlaTγPOOS with different range of noise, b = 1 (top left), b = 10 (top center), b = 20, (top right), and b = 50 (bottom left). Bottom center: the sensitivity of OLOP to different emax parameters. Bottom right: the sensitivity of OLOP to different range of the input noise e R b as parameters while the true b is set to 10.
6. Numerical experiments In this section, we empirically illustrate the benefits of PlaTγPOOS. We chose a simple MDP, shown in Figure 5. In this MDP, a state x ≜ (bin, d) is a pair of a binary variable bin and a non-negative integer d. The MDP has two actions that are also binary. If bin ̸= a, the base reward is 2, in which case, the next state is (a, 0). Otherwise, if bin = a, then r = d and the next state is (a, d + 1). The reward is then shifted by adding 100 to it so that the noises with different ranges can be added on top without making the reward negative. r =#consecutive r =#consecutive visits visits r=2 0
1 r=2
Figure 4 reports the results. All the figures show the cumulative discounted return collected by OLOP and PlaTγPOOS after having interacted for 20 steps with the MDP, having chosen each time an action following their planning strategy and then being transferred to the state resulting of applying the recommended action in the current state; therefore also collecting a reward that is composing the final return. Note that the return reported are shifted in order to not take into account the fixed 100 part of each the reward. The figures in the top row, as well as the figure at the bottom left, reports the comparison between the two returns of OLOP and PlaTγPOOS for different ranges of noise b. PlaTγPOOS is systematically outperforming OLOP while in this case OLOP emax as input, R emax = Rmax and the is given the correct R correct range of the noise eb, that is eb = b. In Figure 4, bottom center and right, we illustrate the sensitivity of OLOP to misleading input parameters. Notice that the performance of OLOP is very vulnerable to these misspecifications while PlaTγPOOS is not using such inputs.
Figure 5. MDP used for our experiments
The initial state is (0, 0). Therefore, the agent has a choice. It can, for instance, remain in the same binary state bin, starting with a null reward but sees its instant reward growing with time if it keeps taking the same action in the future. Alternatively, it could greedily switch to the other binary state bin and obtain a reward of 2 but delaying the hope of obtaining growing reward as in the first scenario. We set γ = 0.95. Therefore, Rmax ≈ 130.
Acknowledgments The research presented was supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, Inria and Otto-von-Guericke-Universität Magdeburg associated-team north-European project Allocate, and French National Research Agency project BoB (grant n.ANR-16-CE23-0003), FMJH Program PGMO with the support of this program from Criteo.
Scale-free adaptive planning for deterministic dynamics & discounted rewards
References Bartlett, P. L., Gabillon, V., and Valko, M. A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption. In Algorithmic Learning Theory (ALT), 2019. Bertsekas, D. and Tsitsiklis, J. Neuro-dynamic programming. Athena Scientific, Belmont, MA, 1996. Bubeck, S. and Munos, R. Open-loop optimistic planning. In Conference on Learning Theory (COLT), 2010. Bubeck, S., Munos, R., Stoltz, G., and Szepesvári, C. X armed bandits. Journal of Machine Learning Research, 12:1587–1627, 2011. Buşoniu, L. and Munos, R. Optimistic planning for Markov decision processes. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2012. Carpentier, A. and Locatelli, A. Tight (lower) bounds for the fixed budget best-arm identification bandit problem. In Conference on Learning Theory (COLT), 2016. Coquelin, P.-A. and Munos, R. Bandit algorithms for tree search. In Conference on Uncertainty in Artificial Intelligence (UAI), 2007. Coulom, R. Efficient selectivity and backup operators in Monte-Carlo tree search. Computers and games, 4630: 72–83, 2007. Feldman, Z. and Domshlak, C. Simple regret optimization in online planning for Markov decision processes. Journal of Artificial Intelligence Research, 2014. Gabillon, V., Ghavamzadeh, M., and Lazaric, A. Bestarm identification: A unified approach to fixed budget and fixed confidence. In Neural Information Processing Systems (NeurIPS), 2012. Gelly, S., Yizao, W., Munos, R., and Teytaud, O. Modification of UCT with patterns in Monte-Carlo Go. Technical report, Inria, 2006. Grill, J.-B., Valko, M., and Munos, R. Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning. In Neural Information Processing Systems (NeurIPS), 2016. Hoorfar, A. and Hassani, M. Inequalities on the lambert w function and hyperpower function. Journal of Inequalities in Pure and Applied Mathematics, 9(2):5–9, 2008. Hren, J.-F. and Munos, R. Optimistic planning of deterministic systems. In European Workshop on Reinforcement Learning, 2008.
Kaufmann, E. and Koolen, W. M. Monte-carlo tree search by best-arm identification. In Neural Information Processing Systems (NeurIPS), 2017. Kocsis, L. and Szepesvári, C. Bandit-based Monte-Carlo planning. In European Conference on Machine Learning (ECML), 2006. Leurent, E. and Maillard, O.-A. Practical Open-Loop Optimistic Planning. arXiv preprint arXiv:1904.04700, 2019. Munos, R. Optimistic optimization of deterministic functions without the knowledge of its smoothness. In Neural Information Processing Systems (NeurIPS), 2011. Munos, R. From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning. Foundations and Trends in Machine Learning, 7(1):1– 130, 2014. Orabona, F. and Pál, D. Scale-free online learning. Theoretical Computer Science, 2018. Orabona, F. and Tommasi, T. Training deep networks without learning rates through coin betting. In Neural Information Processing Systems (NeurIPS), 2017. Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, New York, NY, 1994. Ross, S., Mineiro, P., and Langford, J. Normalized online learning. In Conference on Uncertainty in Artificial Intelligence (UAI), 2013. Shah, D., Xie, Q., and Xu, Z. On reinforcement learning using Monte-Carlo tree search with supervised learning: Non-asymptotic analysis. arXiv preprint arXiv:1902.05213, 2019. Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016. Szörényi, B., Kedenburg, G., and Munos, R. Optimistic planning in Markov decision processes using a generative model. In Neural Information Processing Systems (NeurIPS), 2014. Valko, M., Carpentier, A., and Munos, R. Stochastic simultaneous optimistic optimization. In International Conference on Machine Learning (ICML), 2013.
Scale-free adaptive planning for deterministic dynamics & discounted rewards
A. On the branching factor Proposition 2. κu (ν/2, γ) ≤ κv (ν, γ) ≤ κu (2ν, γ). Proof. For any global optimum and for h ≥ 0, we prove that γh v u Nh (ε) ≤ Nh ε + · 1−γ Let a node a ∈ Ah be such that v(a) ≥ v ⋆ − ε. Then, we have u(a) ≥ v(a) −
γh γh ≥ v⋆ − ε − · 1−γ 1−γ
Similarly, for h ≥ 0, we have that for any global optimum, Nhu (ε) ≤ Nhv
γh · ε+ 1−γ
Using Definition 2, we get the claimed result.
B. PlaTγPOOS is not using a budget larger than n + 1 Notice that for any given depth h ∈ [1 : hmax ], PlaTγPOOS never uses more evaluations than (pmax + 1) hmax h because / hγ 2h ⌉)⌋ ⌊log2 (hmax X⌈ p=0
p 2h hmax hmax h2 γ ≤ log2 (hmax / hγ 2h ) + 1 · p 2h h ⌈h2 γ ⌉ h
Summing over the depths, PlaTγPOOS never uses more evaluations than the budget n + 1 during its depth exploration as 1 + (pmax + 1)
hX max h=1
hmax h
≤ 1 + (pmax + 1)hmax
hX max h=1
1 h
= 1 + hmax log(hmax )(pmax + 1) ≤ 1 + hmax (pmax + 1)2 n ≤ + 1. 2 We need to add the additional evaluation for the cross-validation at the end, pX max h max X
pX max (t + 1)γ 2t hmax n n ≤ ≤ · 2 2 2 (1 − γ ) 2(log2 n + 1) 2 p=0 t=0 p=0
Therefore, the total budget is never more than n/2 + n/2 + 1 = n + 1. Again, notice we use the budget of n + 1 only for the notational convenience, we could also use n/4 for the evaluation in the end to fit under n. Nonetheless, it’s important that the amount of openings is linear in n.
C. Proofs of the lemmas We first define favorable event ξ and prove that it holds with high probability. Lemma 2. Let C be the set of sequence of actions evaluated by PlaTγPOOS during one of its runs. C is a random quantity. Let ξ be the event under which all average estimates for the reward of the state-action pairs receiving at least one evaluation from PlaTγPOOS are within their confidence interval, then P (ξ) ≥ 1 − δ, where ( ) r l k pmax log(4n/δ) p 2(h−1) ξ ≜ ∀a ∈ C, ∀h ∈ [2 : h(a)], p ∈ [0 : pmax ] : if Ta[h] ≥ (h − 1)2 γ , then |b u(a)−u(a)| ≤ b · 2p+1
Scale-free adaptive planning for deterministic dynamics & discounted rewards
Proof. The idea of the proof follows the line of proof of the statement given for StoSOO (Valko et al., 2013). The crucial point is that while we have potentially exponentially many combinations of cells that can be evaluated, given any particular execution we need to consider only a polynomial number of estimators, m, for which we can use a Azuma-Hoeffding concentration inequality. We denote ∀h ∈ [0 : hmax ], p ∈ [0 : pmax ] : ai,h,p ∈ C, the i-th evaluated node of depth h such that ∀t ∈ [2 : h], Tai,h,p ≥ [t] (t − 1)2p γ 2(t−1) . Note that in PlaTγPOOS we have Tai,h,p = hmax . [1]
Though a
i,h,p
is random, we study the quantity u b(a
i,h,p
u b(ai,h,p ) − u(ai,h,p ) =
) − u(ai,h,p ) . We recall that h−1 X
γ t (b rt (ai,h,p ) − rt (ai,h,p ))
(2)
t=0 T i,h,p
=
h−1 X t=0
a [t+1]
γ
t
i,h,p X rbt,s − rt (ai,h,p ) Tai,h,p s=0
(3)
[t+1]
i,h,p This quantity is composed of the elements rbt,s − rt (ai,h,p ) that form a martingale.
Therefore using a Azuma-Hoeffding concentration inequality with a union bound already on the values of T we have v uh−1 X γ 2t log(pmax /δ) u ≥ 1 − δ/pmax P u b(ai,h,p ) − u(ai,h,p ) ≤ bt 2T i,h,p a t=0
[t+1]
Moreover we have for all h ≥ t > 1, γ 2t Tai,h,p
≤
γ 2t 1 γ 2t ≤ = p p 2t p 2t ⌈t2 γ ⌉ t2 γ t2
(4)
[t+1]
2t
1 ≤= 21p for all p ≤ pmax . For t = 0, T γi,h,p = hmax a
[t+1]
Therefore we have r P u b(a
i,h,p
) − u(a
i,h,p
)≤b
log hmax log(?/δ) 2p+1
! ≥ 1 − δ/?
Then we had an extra union bound other all cells that is bounded by n
Lemma 3. For any planning problem with associated (ν, ρ) (see Property 1), on event ξ, for any depths h ∈ [hmax ], for any p ∈ [0 : log2 (hmax /(h2 γ 2h )) ], we have ⊥h,p = h if conditions (1) and (2) simultaneously hold true. p (1) b log(4n/δ)/2p+1 ≤ νρh l m ′
(2) For all h′ ∈ [h], hmax / h′ h′ 2p γ 2h Finally we have ⊥0,p = 0.
′
≥ Cκ(ν, ρ)h .
Proof. We place ourselves on event ξ defined in Lemma 2 and for which we proved that P (ξ) ≥ 1 − δ. We fix p. We prove the statement of the lemma, given that event ξ holds, by induction in the following sense. For a given h and p, we assume the hypotheses of the lemma for that h and p are true and we prove by induction that ⊥h′ ,p = h′ for h′ ∈ [h]. 1◦ For h = 0, we trivially have that ⊥h,p ≥ 0. 2◦ Now consider h′ > 0, and assume ⊥h′ −1,p = h′ − 1 with the objective to prove that ⊥h′ ,p = h′ .
Scale-free adaptive planning for deterministic dynamics & discounted rewards
Therefore, at the end of the processing of depth h′ − 1, during which we were opening the nodes of depth h′ − 1 we managed ′ ′ to open an optimal node that we denote a⋆,h −1 ∈ A⋆,h −1 . Moreover if we consider all the sequence of actions bthat ′ ′ one can build by appending any action in A to a⋆,h −1 ∈ A⋆,h −1 , we have for all such b that Tb[t] ≥ (t − 1)2p γ t−1 for t ∈ [h′ ]. ′
Note that by definition there exist an optimal infinite sequence of actions a⋆ ∈ A⋆ such that a⋆,h −1 = a⋆[h′ −1] j l mk ′ ′ ′ During phase h′ the hmax / h′ h′ 2p γ 2h evaluated nodes from Ah −1 with highest values {b u(ah −1,i )}h′ −1,i are opened. For the purpose of contradiction, let us assume that a⋆[h′ ] is not one of them. This would mean that there exist at j l mk ′ ′ ′ least hmax / h′ h′ 2p γ 2h nodes from Ah , distinct from a⋆[h′ ] , satisfying u b(ah ,i ) ≥ u b(a⋆[h′ ] ) and each verifying (a)
′
Tah′ ,i ≥ ⌈t2p γ t ⌉ for t ∈ [h′ ]. This means that, for these nodes we have: u(ah′ ,i ) + νρh ≥ u(ah′ ,i ) + νρh ≥ u(ah′ ,i ) + [t]
b
p
(b)
(b)
log(4n/δ)/2p+1 ≥ u b(ah′ ,i ) ≥ u b(ah′ ,i⋆h′ ) ≥ u(ah′ ,i⋆h′ ) − b
(a) p ′ log(4n/δ)/2p+1 ≥ u(ah′ ,i⋆h′ ) − νρh ≥ u(ah′ ,i⋆h′ ) − νρh , ′
where (a) is by assumption of the lemma, (b) is because ξ holds. As u(ah′ ,i⋆h′ ) ≥ v ⋆ − νρh by Proposition 1, this j l mk ′ ′ means we have Nhu′ (3νρh ) ≥ hmax / h′ h′ 2p γ h + 1 (the +1 is for ah,i⋆h ). However, by assumption of the l m j k ′ ′ ′ ′ lemma hmax / h′ h′ 2p γ 2h ≥ Cκ(ν, ρ)h . It follows that in general Nhu′ (3νρh ) > Cκ(ν, ρ)h . This leads to having a contradiction with the κu (ν, ρ) with associated constant C as defined in Definition 2. Indeed, the condition j k ′
′
′
Nhu′ (3νρh ) ≤ Cκ(ν, ρ)h in Definition 2 is equivalent to the condition Nhu′ (3νρh ) ≤ Cκ(ν, ρ)h integer.
′
′
as Nhu′ (3νρh ) is an
Lemma 1. For any planning problem with associated (ν, ρ) as in Property 1), on event ξ defined in Appendix C, for any depth h ∈ [hmax ] , for any p ∈ [0 : log2 (hmax /(h2 γ 2h )) ], we have ⊥h,p = h if (1) and (2) simultaneously hold: p (1) b log(4n/δ)/2p+1 ≤ νρh (2) We distinguish cases and express the condition in each: Case 1) h2p γ 2h ≤ 1 : hmax hmax = ≥ Cκ(ν, ρ)h h h ⌈h2p γ 2h ⌉ ′ hmax and for all h′ ∈ [h], ′2 p+1 2h′ ≥ Cκ(ν, ρ)h h 2 γ Case 2) h2p γ 2h ≥ 1 : hmax Case 2.1) γ 2 κu ≥ 1 : 2 p+1 2h ≥ Cκ(ν, ρ)h h 2 γ hmax Case 2.2) γ 2 κu ≤ 1 : 2 p+1 ≥ C h 2 Proof. To prove this statement we show that we verify the hypotheses of Lemma 3. This means we need to just l need to′ m ′ ′ ′ ′ p 2h prove that for all h ∈ [h], hmax / h h 2 γ ≥ Cκ(ν, ρ)h . We first consider the case 2) where h2p γ h ≥ 1. If h = 1 we already know ⊥0,p ≥ 0. Let us now look at the case h > 1. First notice that h2p γ 2h ≥ 1 gives (h − 1)2p γ 2(h−1) ≥ 1. If γ 2 κu ≥ 1 we have that for all h′ ∈ [h − 1], h h′ hmax hmax 2 2 ≥ ≥ C γ κ(ν, ρ) ≥ C γ κ(ν, ρ) h′2 2p+1 h2 2p+1 If h > 1, and if γ 2 κu ≤ 1 we have that for all h′ ∈ [h − 1], h′ hmax hmax 2 ≥ ≥ C ≥ C γ κ(ν, ρ) . h′ 2p+1 h2p+1
Scale-free adaptive planning for deterministic dynamics & discounted rewards
For both γ 2 κu ≤ 1 and γ 2 κu ≥ 1, we then have, hmax hmax ≥ ′ ′ p+1 2h′ h′ ⌈h′ 2p γ 2h′ ⌉ hh2 γ as h2p γ 2h ≥ 1. ′
′ ′ ′2 p+1 2h For both γ 2 κu ≤ 1 and γ 2 κu ≥j 1, the previous equations ≥ k mean that for h ∈ [h − 1], h verifies hmax /h 2 γ ′
′
Cκ(ν, ρ)h ≥ 1. Therefore p ≤ log2 (hmax /(h′2 γ 2h )) .
l m ′ We now consider case 1) where h2p γ 2h ≤ 1. We prove by induction that for all h′ ∈ [h], hmax / h′ h′ 2p γ 2h ≥ ′
Cκ(ν, ρ)h . 1◦ By assumption of the lemma we say: hmax / h h2p γ 2h ≥ Cκ(ν, ρ)h l m ′ ′ ′ 2◦ We further assume hmax / h′ h′ 2p γ 2h ≥ Cκ(ν, ρ)h is true for some h′ ≤ h with h′ 2p γ 2h ≤ 1 We want to prove that either: ′
both (h′ − 1)2p γ 2(h −1) ≤ 1 ′
max and (h′ −1) (h′h−1)2 ≥ Cκ(ν, ρ)h −1 p γ 2(h′ −1) ⌈ ⌉ ′
or (h′ − 1)2p γ 2(h −1) ≥ 1 l m l m ′′ ′′ ′ then hmax / (h′′ ) (h′′ )2p γ 2(h ) ≥ Cκ(ν, ρ)h is already true for all h′′ ∈ [h′ ]. If (h′ − 1)2p γ 2(h −1) = 1 then we have ′ ′ hmax hmax ≥ ≥ Cκ(ν, ρ)h ≥ Cκ(ν, ρ)h −1 ′ ′ (h − 1) h
l m ′ If (h′ − 1)2p γ 2(h −1) > 1, then we have that l m ′ hmax / h′ (h′ − 1)2p γ 2(h −1) ≥ ′ ′ hmax / (h′ − 1)2 2p+1 γ 2(h −1) ≥ Cκ(ν, ρ)h −1 l m ′′ ′′ Using this inequality we can now use Case 2) to have that: hmax / (h′′ ) (h′′ )2p γ 2(h ) ≥ Cκ(ν, ρ)h is already true for all h′′ ∈ [h′ ]. ′ ′ The previous equations mean that for h′ ∈ [h − 1], h′ verifies hmax / h′2 2p+1 γ 2h ≥ Cκ(ν, ρ)h ≥ 1. Therefore j k ′ p ≤ log2 (hmax /(h′2 γ 2h )) .
D. Proof of Theorem 3 and Theorem 4 Theorem 3. High-noise regime If the noise b is high enough to verify both high-noise conditions as defined in the caption of Table 1, then after n rounds, for any problem with associated (ν, ρ), and branching factor κ ≜ κu (ν, ρ), the simple regret of PlaTγPOOS obeys 1 e n2 − 2 if γ 2 κ ≤ 1, O b Ern = log(1/ρ) n − log(γ 2 κ/ρ2 ) e if γ 2 κ > 1. O b2
Scale-free adaptive planning for deterministic dynamics & discounted rewards
Theorem 4. Low-noise regime If the noise b is low enough to verify both high-noise conditions as defined in the caption of Table 1, then after n rounds, for any problem with associated (ν, ρ), and branching factor κ ≜ κu (ν, ρ), the simple regret of PlaTγPOOS obeys e (νρn ) O if κ = 1, log(1/ρ) Ern = − log(κ) e ν n2 O if κ > 1. b
Proof of Theorem 3 and Theorem 4. We first place ourselves on the event ξ defined in Lemma 2 and where it is proven that P (ξ) ≥ 1 − δ. We bound the simple regret of PlaTγPOOS on ξ. Step 1) General definition of the regret √ for the bound. We consider a problem with associated (ν, ρ). For simplicity we write κ = κu (ν, ρ). We chose δ = R4b(1−δ) max n We have for all p ∈ [0 : pmax ]
s
pmax log(Rmax n3/2 /b) 2hmax s b pmax log(Rmax n3/2 /b) (a) ≥ u(an ) + ≥u b(an ) 2 1−γ 2hmax (c) (b) ≥u b(ap ) ≥ u b ap[⊥h ,p +1] max s (a) b pmax log(Rmax n3/2 /b) ≥ u ap[⊥h ,p +1] − 2 max 1−γ 2hmax s (d) b pmax log(Rmax n3/2 /b) ≥ v ⋆ − νρ⊥hmax ,p +1 − 1 − γ2 2hmax
b v(an ) + 1 − γ2
2t
hmax where (a) is because the actions at time t, at (n, p), of the candidate a(n, p) have been evaluated (t+1)γ times (1−γ)2 p • p 2(t−1) and because ξ holds, (b) is because a[⊥h ,p +1] ∈ {a ∈ A : ∀t ∈ [2 : h(a)], Ta[t] ≥ (t − 1)2 γ } and max ap = arg max u b(a), (c) is because an = arg max u b(ap ), and (d) is by Assumption 1. {ap ,p∈[0:pmax ]} a∈A• :∀t∈[2:h(a)],Ta[t] ≥⌈(t−1)2p γ 2(t−1) ⌉ q pmax log(Rmax n3/2 /b) b From the previous inequality we have rn = v ⋆ − Q⋆ (x, an ) ≤ νρ⊥hmax ,p +1 + 2 1−γ , for p ∈ [0 : 2 2hmax pmax ].
Step 2) Defining some important depths For the rest of proof we want to lower bound maxp∈[0:pmax ] ⊥hmax ,p . Lemma 3 and 1 provide some sufficient conditions on p and h to get lower bounds. These conditions are inequalities in which as p gets smaller (fewer samples) or h gets larger (more depth) these conditions are more and more likely not to hold. For our bound on the regret of PlaTγPOOS to be small, we want quantities p and h where the inequalities hold but using as few samples as possible (small p) and having h as large as possible. Therefore we are interested in determining when the inequalities flip signs which is when they turn to equalities. This is what we solve next. δ,Rmax We set the notation gn,b = pmax log(Rmax n3/2 /b(1 − δ)).
In its most general form we are interested in the real numbers e h and pe are such that e h is the larger real number such that for ′ all h ≤ e h s hmax ≥ Cκ(ν, ρ)h while h2 2pe+1 γ 2h
b
δ,Rmax gn,b
2pe
= νρh e
(5)
Scale-free adaptive planning for deterministic dynamics & discounted rewards
In the case γ 2 κ ≥ 1 we can simply solve the following equations. We denote e h1 , pe1 the real numbers satisfying s δ,Rmax e gn,b hmax ν 2 ρ2h1 e e h1 = Cκ and b = νρh1 γ 2 . δ,Rmax 2e p e1 2 2 h −2 e 2 1 γ 2h b g 1
(6)
n,b
In the case γ 2 κ ≤ 1 the previous equation can possess two solutions where the largest of these two solutions will not verify Equation 5. Additionally the smallest solution might be hard to express in a close form when γ 2 κ ≤ 1. Therefore for simplicity we define for the case γ 2 κ ≤ 1, e h2 , pe2 the real numbers satisfying s δ,Rmax e gn,b hmax ν 2 ρ2h2 e = C and b = νρh2 . (7) e 2pe2 2h22 b2 g δ,Rmax n,b
e h2 and pe2 are defined for the case γ 2 κ ≤ 1. Our approach is to solve h1 and pe1 are defined for the case γ 2 κ ≥ 1 while e Equation 6 and 7 and then verify that it gives a valid indication of the behavior of our algorithm in term of its optimal p and h. We have ! s 2ν2h 2 γ max e W log(γ 2 κ/ρ2 )/2 h1 = δ,Rmax log(γ 2 κ/ρ2 ) 2Cb2 gn,b ! s 2h ν 2 max e h2 = W log(1/ρ2 )/2 δ,Rmax log(1/ρ2 ) 2Cb2 gn,b where standard W is the Lambert W function. h which would lead to a However after a close look at the Equation 7, we notice that it is possible to get values of pe and e p e e h e number of evaluations h2 γ < 1. This actually corresponds to an interesting case when the noise has a small range and where we can expect to obtain an improved result, that is: obtain a regret rate close to the deterministic case. This low range of noise case then has to be considered separately. Therefore, we distinguish two cases which corresponds to different noise regimes depending on the value of b. Looking at e 2 2h e the equation on the right of (7), we have that e > 1. Based on this condition we now consider the h2peγ h < 1 if e ν ρδ,R γ 2h e hb2 gn,b max
two cases. However for both of them we define some generic ḧ and p̈. Case 1) γ 2 κ ≥ 1 :
Note that in this case then κ > 1. We subdivide this case into multiple subcases:
Case 1.1) Noise regime
ν 2 ρ2h1 e
e δ,Rmax γ 2h1 e h1 b2 gn,b e ν 2 ρ2h1
≤1
Case 1.1.1) High-noise regime b2 gδ,Rmax ≤ 1 n,b
2 2h1 ρ In this case, we denote ḧ1 = e h1 and p̈1 = pe1 . As b2νgδ,R ≤ 1 by construction, we have pe1 ≥ 0. Using standard properties max e
n,b
of the ⌊·⌋ function, we have s b
s
δ,Rmax gn,b ≤b 2⌊ep1 ⌋+1
δ,Rmax gn,b
2pe1
≤ νρh1 ≤ νρ⌊h1 ⌋ e
e
hmax hmax and, j k j k ≥ j kj k e e 2 h e e h1 e h1 2⌊ep1 ⌋+1 γ ⌊ 1 ⌋ h1 e h1 2pe1 +1 γ 2⌊h1 ⌋ hmax hmax ν 2 ρ2h1 ≥j k = δ,Rmax 2e e 2e h21 b2 gn,b γ h1 h1 e h1 2pe1 +1 γ 2eh1 −2 e
= Cκh1 ≥ Cκ⌊h1 ⌋ . e
e
(8)
Scale-free adaptive planning for deterministic dynamics & discounted rewards
j k We will verify that ḧ is a reachable depth by PlaTγPOOS in the sense that ḧ ≤ hmax and ⌊p̈⌋ ≤ log2 (hmax /(h2 γ 2h )) ≥ Cκḧ , we have ḧ2 γ 2ḧ ≤ hmax /2p̈ . and . As κ < 1, and ḧ ≥ 0 we have κḧ ≥ 1. This gives Cκḧ ≥ 1. Finally as ḧ2h2max p̈ γ 2ḧ e 2 2h 1
ρ Case 1.1.2) Low-noise regime 1 b2νgδ,R ≥1 max n,b
We denote ḧ = h1 and p̈ = p1 where h and p verify, hmax 2 2h1 γ 2h1
Again,
hmax 2 2h1 2p1 γ 2h1
= Cκh1
and
p1 = 0.
(9)
≥ 1. 2 h1 = W log(γ 2 κ)
r 2
log(γ κ)/2
hmax 2C
!
Using standard properties of the ⌊·⌋ function, we have s δ,Rmax q gn,b e (a) δ,Rmax b ≤ b gn,b < νρh1 ≤ νρh1 ≤ νρ⌊h1 ⌋ ⌊ p̈ ⌋+1 2 1 where (a) is because of the following reasoning. As we have
hmax ν 2 ρ2h1 e δ,Rmax 2h 2e h21 b2 gn,b γ 1 e
(10) e 2 2h 1
ρ ≥ 1, then, = Cκh1 and b2νgδ,R max e
n,b
hmax e 2e h21 γ 2h1
≤
h1 2h1 h1 2h1 Cκh1 . From the inequality hmax and the fact that h1 corresponds to the case of equality hmax γ , 2 = Cκ e 2 ≤ Cκ γ e
e
e
2h1
2h1
we deduce that h1 ≤ e h1 , since the left term of the inequality decreases with h while the right term increases (as γ 2 κ ≥ 1). e e Having h1 ≤ h1 gives ρh1 ≥ ρh1 . Moreover, the term log(γ 2 κ) of h1 could lead to think that we could potentially obtain a better rate that in the deterministic case where the term is log(γ 2 κ). However this is not true because as h1 is the solution of h1 = h2max = Cκh1 and we 2h1 2h1 γ
h3 have by assumption in this case h1 γ2h1 ≥ 1 then h1 ≤ h3 where h3 is defined as the solution of h3 = 2hhmax . 2h3 = Cκ 3γ hmax 1 We have h3 = log(κ) W log(κ) 2C . Therefore one can see that this rate is not better that the deterministic rates.
Case 1.2) Low noise regime 2
ν 2 ρ2h1 2 δ,Rmax 1 b gn,b e
e γ 2h1 e h
≥1
We denote ḧ = b h1 and p̈ = pb1 where b h and pb verify, hmax b = Cκh1 2b h1 b h1 =
and pb1 = max(0, pe1 )).
1 W log(κ)
hmax log(κ) 2C
(11)
Using standard properties of the ⌊·⌋ function, we have s s δ,Rmax δ,Rmax gn,b gn,b b e (a) b b < νρh1 ≤ νρh1 ≤ νρ⌊h1 ⌋ ≤ b p e ⌊ p̈ ⌋+1 1 1 2 2 where (a) is because of the following reasoning. As we have hmax ≤ Cκ 2e h1
hmax ν 2 ρ2h1 e δ,Rmax 2h 2e h21 b2 gn,b γ 1 e
= Cκh1 and e
(12) ν 2 ρ2h1 e
e δ,Rmax γ 2h1 e h1 b2 gn,b
≥ 1, then,
b . From the inequality hmax ≤ Cκ and the fact that b h1 corresponds to the case of equality hmax = Cκh1 , we 2e h1 2b h1 deduce that b h1 ≤ e h1 , since the left term of the inequality decreases with h while the right term increases . Having b h1 ≤ e h1 e h1
e h1
gives ρh1 ≥ ρh1 . b
e
Scale-free adaptive planning for deterministic dynamics & discounted rewards
Case 2) γ 2 κ ≤ 1 Case 2.1) Noise regime
ν 2 ρ2h e
e e 2 δ,Rmax γ 2h hb gn,b e 2 2h
≤1 2
ρ Case 2.1.1) High-noise regime b2νgδ,R ≤1 max n,b
2 2h2 ρ ≤ 1 by construction, we have pe2 ≥ 0. Using standard properties In this case, we denote ḧ = e h2 and p̈ = pe2 . As b2νgδ,R max e
n,b
of the ⌊·⌋ function, we have s b
s
δ,Rmax gn,b
2
≤b ⌊e p ⌋+1
δ,Rmax gn,b
2pe2
2
= νρh2 ≤ νρ⌊h2 ⌋
(13)
e
e
hmax hmax and, j k j k ≥ j kj k ⌊e p ⌋+1 e e e h2 h2 2 2 h2 e h2 2pe2 +1 ≥
hmax
hmax ν 2 ρ2h2 2e h2 b2 g δ,Rmax e
e h22 2pe2 +1
=
2
n,b
= C. j k We will verify that ḧ is a reachable depth by PlaTγPOOS in the sense that ḧ ≤ hmax and ⌊p̈⌋ ≤ log2 (hmax /(h2 γ 2h )) . As κ < 1, and ḧ ≥ 0 we have κḧ ≥ 1. This gives Cκḧ ≥ 1. Finally as ḧ2h2max ≥ Cκḧ , we have ḧ2 γ 2ḧ ≤ hmax /2p̈ . p̈ γ 2ḧ e 2 2h 2
ρ Case 2.1.2) Low-noise regime 1 b2νgδ,R ≥1 max n,b
We denote ḧ = h2 and p̈ = p2 where h and p verify, hmax 2
=C
and
2h2 Again,
hmax 2 2h2 2p2 γ 2h2
p2 = 0.
(14)
≥ 1. r h2 =
hmax 2C
Using standard properties of the ⌊·⌋ function, we have s δ,Rmax q gn,b e (a) δ,Rmax b ≤ b gn,b < νρh1 ≤ νρh2 ≤ νρ⌊h2 ⌋ ⌊ p̈ ⌋+1 2 2 e 2 2h 2
(15)
e 2 2h 2
ν ρ ρ where (a) is because of the following reasoning. As we have hemax = C and b2νgδ,R ≥ 1, then, hmax max 2 2 δ,Rmax e 2 ≤ C. From 2h2 b gn,b
n,b
2h2
hmax e the inequality hmax 2 = C, we deduce that h2 ≤ h2 , since e 2 ≤ C and the fact that h2 corresponds to the case of equality 2h2
2h2
e the left term of the inequality decreases with h while the right term stays constant. Having h2 ≤ e h2 gives ρh2 ≥ ρh2 .
Case 2.2) Low noise regime 2
ν 2 ρ2h e e 2 δ,Rmax γ 2h hb gn,b e
≥1
We denote ḧ = b h2 and p̈ = pb2 where b h and pb verify, hmax b = Cκh2 b h2 b h2 =
1 W log(κ)
hmax log(κ) C
(16)
Scale-free adaptive planning for deterministic dynamics & discounted rewards
By construction, we have e h2 ≤ e h. We set pb2 = max(0, pe)).
(17)
Using standard properties of the ⌊·⌋ function, we have s b
s
δ,Rmax gn,b
≤b 2⌊p̈2 ⌋+1
δ,Rmax gn,b
2pe
e (a)
= νρh ≤ νρh2 ≤ νρ⌊h2 ⌋
(18)
b
b
e 2 2h
ν ρ = Cκh and where (a) is because of the following reasoning. As we have e2 h2max δ,Rmax 2h e h b gn,b
e
γ
ν 2 ρ2h e
e e 2 δ,Rmax γ 2h hb gn,b
≥ 1, then,
e e b hmax ≤ κh . From the inequality hmax ≤ Cκh and the fact that b h2 corresponds to the case of equality hmax = Cκh2 , we e e h h 2b h2
deduce that b h2 ≤ e h, since the left term of the inequality decreases with h while the right term increases. Having b h2 ≤ e h b e h2 h gives ρ ≥ ρ . Step 3 Given these particular definitions of ḧ and p̈ in two distinct cases we now bound the regret. j k We always have ⊥hmax ,⌊p̈⌋ ≥ 0. If ḧ ≥ 1, as discussed above ḧ ∈ [hmax ], therefore ⊥hmax ,⌊p̈⌋ ≥ ⊥⌊ḧ⌋,⌊p̈⌋ , as ⊥·,⌊p⌋ is increasing jfork all p ∈ [0, pmax ]. Moreover on event ξ, and for the cases j k1.1.1, 1.1.2, 2.1.1 and 2.1.2 described above, ⊥⌊ḧ⌋,⌊p̈⌋ = ḧ because of Lemma 1 (Case 2)) which assumptions on ḧ and ⌊p̈⌋ are verified in each cases as j k detailed above and, in general, ḧ ∈ hmax /2p̈ and ⌊p̈⌋ ∈ [0 : pmax ]. So, for the aforementioned cases, we have j k j k ⊥⌊hmax /2p̈ ⌋,⌊p̈⌋ ≥ ḧ . Very similarly cases 1.2 and 2.2. lead to ⊥⌊hmax /2p̈ ⌋,⌊p̈⌋ ≥ ḧ by using Lemma 1 (Case 1)). We bound the regret now discriminating on whether or not the event ξ holds. We have s
rn ≤ (1 − δ) νρ⊥hmax ,p̈ +1 + 2 s ≤ νρ
⊥hmax ,p̈ +1
b 1 − γ2 δ,Rmax gn,b
b +2 1 − γ2
2hmax s
δ,Rmax gn,b
b ≤ νρ⊥hmax ,p̈ +1 + 6 1 − γ2
hmax
δ,Rmax gn,b
2hmax
+ δ × Rmax 1−γ
4b +√ n ·
We can now bound the regret in the two regimes. Case 1) γ 2 κ ≥ 1 :
Note that in this case then κ > 1. We subdivide this case into multiple subcases:
Case 1.1) Noise regime
ν 2 ρ2h1 e
e δ,Rmax γ 2h1 e h1 b2 gn,b
≤1
Case 1.1.1) High-noise regime In general,we have
s
2 W log(γ 2 κ/ρ2 )/2 log(γ 2 κ/ρ2 )
rn ≤ νρ
γ 2 ν 2 hmax δ,Rmax 2Cb2 g n,b
s b +6 1−γ
δ,Rmax gn,b
hmax
·
Moreover, as proved by Hoorfar & Hassani (2008), the Lambert W (x) function verifies for x ≥ e, W (x) ≥ log
x log x
.
Scale-free adaptive planning for deterministic dynamics & discounted rewards
r γ 2 ν 2 hmax Therefore, if log(γ κ/ρ )/2 2Cb > e we have, 2 g δ,Rmax 2
2
n,b
s rn − 6
b 1−γ
δ,Rmax gn,b
hmax
2 log log(γ 2 κ/ρ2 )
≤ νρ
1 log log(γ 2 κ/ρ2 )
= νe
v u log(γ 2 κ/ρ2 )/2u t
γ 2 ν 2 hmax δ,Rmax 2Cb2 g n,b v u 2 ν 2 hmax γ u loglog(γ 2 κ/ρ2 )/2t δ,Rmax 2Cb2 g n,b
γ 2 ν 2 hmax δ,Rmax 2Cb2 g n,b log(ρ) v u γ 2 ν 2 hmax u 2 2 2 log log(γ κ/ρ )/2t δ,Rmax 2Cb2 g n,b log2 (γ 2 κ/ρ2 )/2
log(ρ) log(γ 2 κ/ρ2 )
2 2
=ν
γ ν hmax log2 (γ 2 κ/ρ2 )/2 2Cb 2 g δ,Rmax n,b
log
r
2
log(γ 2 κ/ρ2 )/2
γ 2 ν 2 hmax δ,Rmax 2Cb2 gn,b
!
.
e 2 2h 1
ρ ≥1 Case 1.1.2) Low-noise regime 1 b2νgδ,R max n,b
rn ≤ νρ
2 W log(γ 2 κ)
2
log(γ κ)/2
s
√ hmax +6
2C
b 1−γ
δ,Rmax gn,b
hmax
·
Moreover, as proved by Hoorfar & Hassani (2008), the Lambert W (x) function verifies for x ≥ e, W (x) ≥ log q max Therefore, if log(γ 2 κ)/2 h2C > e we have, s b rn − 6 1−γ
δ,Rmax gn,b
hmax
2 log log(γ 2 κ)
≤ νρ
1 log log(γ 2 κ)
= νe =ν r We have 6b
δ,Rmax gn,b hmax
≤6
h1 q νρ
r
e
δ,Rmax gn,b
r Therefore rn ≤ νρ
⊥hmax ,p +1
+ 6b
Case 1.2) Low noise regime 2
hmax
√2Ch
max 2C
log(ρ)
log(γ κ)
max log2 (γ 2 κ)/2 h2C q max log2 log(γ 2 κ)/2 h2C
δ,Rmax gn,b hmax
δ,Rmax gn,b hmax e
log2 (γ 2 κ)/2 log2 log(γ 2 κ)/2
max 2C
log(ρ) 2
≤ 6νρh1 ≤ 6νρh1 . e
≤ 7νρh1 .
ν 2 ρ2h1 2 δ,Rmax 1 b gn,b
e γ 2h1 e h
√h max √ 2C h
log(γ 2 κ)/2 log log(γ 2 κ)/2
≥1
.
x log x
.
Scale-free adaptive planning for deterministic dynamics & discounted rewards
s b 1−γ
rn − 6
2 2h1 ρ Moreover if b2νgδ,R max n,b e
r ≥ 1, we have 6b r
Therefore rn ≤ νρ
⊥hmax ,p +1
+ 6b
δ,Rmax gn,b
hmax
δ,Rmax gn,b hmax
δ,Rmax gn,b hmax
≤6
log(ρ)
log(κ) hmax log(κ) 2C ≤ν . log(κ) log hmax2C
r
h1 q νρ e
δ,Rmax gn,b
δ,Rmax gn,b hmax
≤ 6νρh1 ≤ 6νρh1 . e
b
≤ 7νρh1 . b
Case 2) γ 2 κ ≤ 1 Case 2.1) Noise regime
ν 2 ρ2h e e 2 δ,Rmax γ 2h hb gn,b e
≤1
e 2 2h 2
ρ ≤1 Case 2.1.1) High-noise regime b2νgδ,R max n,b
− 12
s b rn − 6 1−γ
2
δ,Rmax gn,b
hmax
≤ν
max log2 (1/ρ2 )/2 2Cbν2 ghδ,R max n,b
log
2
r 2 max log(1/ρ2 )/2 2Cbν2 ghδ,R max
!
.
n,b
e 2 2h 2
ρ ≥1 Case 2.1.2) Low-noise regime 1 b2νgδ,R max n,b
Here with a similar reasoning as in the case 1.1.2) we have rn ≤ 7νρh1 ≤ 7νρ Case 2.2) Low noise regime 2
e 2 2h
ν ρ e e 2 δ,Rmax hb gn,b γ 2h
b 1−γ
2 2h ρ Moreover if b2 gνδ,R max n,b e
r ≥ 1, we have 6b r
Therefore rn ≤ νρ
⊥hmax ,p +1
+ 6b
Moreover if κ = 1 then rn ≤ 7νρ
δ,Rmax gn,b
hmax
δ,Rmax gn,b hmax
δ,Rmax gn,b hmax
2C
.
≥1
s rn − 6
√ hmax
≤6
log(ρ)
log(κ) hmax log(κ) C ≤ν . log hmaxClog(κ)
h q νρ e
δ,Rmax gn,b
r
δ,Rmax gn,b hmax
≤ 6νρh ≤ 6νρh2 . e
b
≤ 7νρh1 . b
hmax C
E. Use of the budget Remark 1. The algorithm can be made anytime and agnostic to n using the standard doubling trick. Remark 2 (More efficient use of the budget). Because of the use of the floor functions ⌊·⌋, the budget used in practice can be significantly smaller than n. While this only affects numerical constants in the bounds, in practice, it can noticeably influence the performance. Therefore one should consider, for instance, having hmax replaced by c × hmax with c been the largest number such that the budget is still smaller than n. Additionally, the use of the budget n could be slightly optimized by taking into account that the necessary number of pulls at depth h cannot be larger than K h .