N EAR -O PTIMAL R EINFORCEMENT L EARNING WITH M ULTI -S TEP T RANSITION L OOKAHEAD
arXiv:2609.11807v1 [stat.ML] 10 Sep 2026
Corentin Pla CREST, ENSAE Criteo AI Lab FairPlay Joint Team [email protected]
Hugo Richard Criteo AI Lab FairPlay Joint Team [email protected]
Marc Abeille Criteo AI Lab FairPlay Joint Team [email protected]
Vianney Perchet CREST, ENSAE Criteo AI Lab FairPlay Joint Team [email protected]
A BSTRACT We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of ℓ actions before deciding its course of action. Although look-ahead can substantially improve achievable performance, it is known that optimal planning with multi-step transition look-ahead is NP-hard, but this hardness was established using discount factors arbitrarily close to one. It was therefore unknown whether the problem remains hard for any discount factor, and whether near-optimal planning can nevertheless be performed efficiently. We resolve both questions. First, we show that for every fixed rational discount factor (γ ∈ (0, 1)), exact planning remains NPhard. Second, we introduce a randomized polynomial-time approximation scheme for every fixed look-ahead depth. We then extend our approach to unknown transitions and stochastic rewards using optimism and variance-adaptive confidence bounds. The resulting algorithm achieves cumulative regret whose leading term matches classical tabular discounted RL up to logarithmic factors. Thus, although exact planning with transition look-ahead is NP-hard, efficient near-optimal planning and learning remain possible.
1
I NTRODUCTION
Reinforcement Learning (RL) (Sutton & Barto, 2018) addresses the problem of learning how to act in a dynamic environment. This problem is modeled via a Markov Decision Process (MDP) which involves a transition kernel, describing how states of the environment evolve in response to the agent’s actions, and a reward function, providing feedback to the agent for taking a particular action in a given state. The agent’s goal is to select actions that maximize the cumulative collected reward called return, accounting not only for immediate gains but also for the long-term impact of its decisions on the state dynamics (Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018). In this work, we focus on stationary MDP, in which the reward function and transition kernel are independent of time. In the standard RL framework, the reward and the next state are revealed only after an action has been taken. However, RL with transition look-ahead assumes that, in addition to this underlying dynamical model, extra predictive information is available at decision time: the agent observe before taking its action, which states would be visited upon playing any sequence of actions of length ℓ. This captures situations where one benefits from privileged information channels beyond standard interaction. A typical example is collaborative navigation systems that allow real-time traffic information (e.g., Waze, Coyote...) where information from nearby drivers can be used to estimate future position, speed, and traffic conditions given a sequence of routing decisions (Vasserman et al., 2015). 1
Other examples include access to high-fidelity but expensive simulators that can provide look-ahead on demand, or supply-chain systems where estimated delivery or arrival times are provided in advance. Standard RL algorithms do not come with off-the-shelf tools to incorporate look-ahead, and a naive policy would be to just discard this additional information which is sub-optimal. Related work. The idea of augmenting reinforcement learning with look-ahead information has recently gained attention. Merlis (2024) introduced a pseudo-polynomial algorithm for one-step transition look-ahead in the finite-horizon setting, while Merlis et al. (2024) studied general lookahead horizons for reward look-ahead, focusing on the value of additional information. Closer to our setting, Pla et al. (2026a) studied the computational complexity of perfect transition look-ahead in stationary MDPs, showing that planning is polynomial-time solvable for ℓ = 1 but NP-hard for every ℓ ≥ 2. Lu et al. (2025) considered discounted MDPs with imperfect and partially available transition look-ahead and proposed BOLA, an algorithm that uses a ℓ-step transition prediction to select a sequence of ℓ actions before replanning. This procedure does not in general implement the optimal adaptive policy in our transition-look-ahead model, where the agent observes an updated look-ahead window and makes a new decision at every time step. Our hardness result also connects to the broader literature on the computational complexity of MDP planning. Classical planning in stationary MDPs is polynomial-time solvable under the discounted criterion, with foundational complexity results due to Papadimitriou (1987); subsequent work has further investigated the complexity of MDP planning under different objectives and horizons (Mundhenk et al., 2000; Littman et al., 2013; Balaji et al., 2018; Chen & Wang, 2017). Beyond these classical formulations, changes in the information structure can fundamentally alter computational complexity. For instance, Walsh et al. (2009) show that planning with delayed feedback can become NP-hard because of the exponential blow-up of the augmented state space, while partial observability leads to even stronger hardness results (Papadimitriou, 1987). Transition look-ahead exhibits a complementary phenomenon: providing additional information also induces a large augmented state space and makes exact planning intractable. Our positive result therefore belongs to a complementary algorithmic question: whether such exponentially large planning problems can nevertheless be approximated without explicitly solving the augmented MDP. In this respect, our approach is related to sampling-based and empirical methods for approximate planning. Kearns et al. (2002) introduced sparse sampling, which computes near-optimal actions by exploring only a randomly sampled portion of the full look-ahead tree. This method has a complexity that is exponential in the effective horizon (1 − γ)−1 , whereas our algorithm has polynomial complexity in (1 − γ)−1 for fixed look-ahead depth ℓ. Our method can be viewed as a dynamicprogramming analogue of sample-average approximation (Kleywegt et al., 2002): a fixed sample of complete transition tables replaces the Bellman expectations and induces a closed empirical planning problem. Unlike classical SAA, this problem is solved once during preprocessing, and its solution extends with a uniform guarantee to any look-ahead window observed at deployment. The look-ahead information exploited by our policy can also be viewed as prediction available to the decision maker before acting, this connects our setting to the growing literature on algorithms with predictions (Mitzenmacher & Vassilvitskii, 2020; Benomar et al., 2025; Benomar & Perchet, 2025; Merlis et al., 2023). These works study how side information can be used to improve upon worst-case performance, often through trade-offs between consistency (when predictions are accurate) and robustness (when they are not). This perspective has recently been explored in several sequential decision-making settings. Li et al. (2024) design a learning-augmented controller for LQR with latent perturbations, where accurate predictions lead to near-optimal performance while robustness to prediction errors is retained. Lyu et al. (2026) study discounted MDPs equipped with predictions of the transition matrix and show that such predictions can reduce sample complexity, while Li et al. (2023) establish consistency–robustness trade-offs when the advice is provided in the form of predicted Q-values in non-stationary MDPs. Another line of work studies MDPs with exogenous information or dynamics. Pla et al. (2026b) consider discounted MDPs with i.i.d. exogenous contexts that are revealed before the agent acts and derive minimax PAC guarantees that exploit this structure, while Maran et al. (2026) study MDPs markovian exogenous contexts and show that this structure can substantially improve learning guarantees. Contribution. We resolve two open questions concerning planning with multi-step transition look-ahead. First, we show that the known NP-hardness does not rely on a large effective hori2
zon: for every fixed rational discount factor γ ∈ (0, 1), exact planning remains NP-hard for ℓ ≥ 2 (Theorem 1). Second, for every fixed look-ahead depth ℓ, we give a randomized polynomial-time approximation scheme that constructs, with high probability, a uniformly near-optimal policy (Theorem 2).We further extend our approach to unknown transitions and stochastic rewards with a regret learning algorithm (Theorem 3).
2
S ETTING AND OBJECTIVES
2.1
M ARKOV D ECISION P ROCESSES
We study finite tabular Markov decision processes (MDP) M = (S, A, P, r), where S is a finite state space |S| = n, A is a finite action space |A| = m, P (s′ | s, a) denotes the probability of reaching state s′ ∈ S after taking action a ∈ A in state s ∈ S, and r : S × A → [0, Rmax ] is the reward function. A (possibly randomized) stationary memoryless policy is a mapping π : S → ∆(A), where ∆(A) denotes the simplex over A. Under such a policy, the interaction evolves as follows: at each time t ∈ N, the system is in state st ∈ S, the agent selects an action at ∼ π(· | st ), receives reward r(st , at ), and the next state is sampled according to st+1 ∼ P (· | st , at ). We consider the standard discounted-return objective (Puterman, 2014, Chapter 6). For a discount factor γ ∈ (0, 1) and an initial state s ∈ S, the value of a policy π is V π (s) = P∞ π E [ t=0 γ t r(st , at ) | s0 = s] . The optimal discounted value function is defined by V ∗ (s) = supπ V π (s), ∀s ∈ S, where the supremum is taken over stationary memoryless policies. The ∗ optimal value function V ∗ is the unique solution n o to the Bellman optimality equations: V (s) = P maxa∈A r(s, a) + γ s′ ∈S P (s′ | s, a) V ∗ (s′ ) , ∀s ∈ S. 2.2
T RANSITION LOOK - AHEAD
We now formalize the extra information provided by the look-ahead in terms of state observability and provide an augmented MDP construction that allows us to embed this problem into the standard evaluation framework introduced above. 2.2.1
L OOK - AHEAD AND STATE OBSERVABILITY
A convenient generative view of the transition kernel is the following. At each time t, for every state-action pair (s, a), the environment independently draws a potential successor Θt (s, a) ∼ P (· | s, a), collecting these draws defines a random transition table Θt : S × A → S, taking values in Ω := S S×A , Its distribution Q is therefore Y Q(θ) := P θ(s, a) | s, a (1) (s,a)∈S×A
We let (Θt )t≥0 be an i.i.d. sequence of distribution Q. In a standard MDP, Θt is hidden from the agent and, after action At is selected, the realized transition is simply St+1 = Θt (St , At ). Transition look-ahead changes the information available before acting. At time t, the environment reveals some of the tables Θt , Θt+1 , . . . to the agent. Definition 1 (ℓ-step transition look-ahead). Let ℓ ≥ 1. At each decision time t, an agent with ℓ-step transition look-ahead observes, before choosing At , the window Ctℓ := (Θt , Θt+1 , . . . , Θt+ℓ−1 ) ∈ Ωℓ .
(2)
This window encodes the complete depth-ℓ transition tree rooted at the current state. Indeed, starting from s0 = St , any action sequence a0 , . . . , ak−1 , with k ≤ ℓ, determines the trajectory sj+1 = Θt+j (sj , aj ), j = 0, . . . , k − 1. Thus, Ctℓ reveals the outcome of every action sequence of length at most ℓ before the first action is chosen. In particular, for ℓ = 1, the agent knows the successor Θt (St , a) of every action a ∈ A. After one transition, the oldest table is discarded and a fresh independent table is revealed, so that ℓ Ct+1 = (Θt+1 , . . . , Θt+ℓ−1 , Θt+ℓ ), with Θt+ℓ ∼ Q independent of the previous tables. Hence, the pair (St , Ctℓ ) evolves as a Markov process on S × Ωℓ , allowing the transition look-ahead problem to be treated as a standard discounted MDP on this augmented state space. 3
2.2.2
P OLICIES AND VALUE FUNCTIONS
A stationary policy with ℓ-step transition look-ahead acts on the augmented state and is therefore a mapping π : S × Ωℓ → ∆(A). Its value at an observed state-window pair (s, c) ∈ S × Ωℓ , with P∞ t ℓ c = (θ0 , . . . , θℓ−1 ), is Vℓπ (s, c) := Eπ t=0 γ r(St , At ) S0 = s, C0 = c . We denote the optimal value by Vℓ⋆ (s, c) := supπ Vℓπ (s, c). For any bounded function V : S × Ωℓ → R, define the Bellman optimality operator (Tℓ V )(s, θ0 , . . . , θℓ−1 ) := maxa∈A r(s, a) + γEΘ∼Q V θ0 (s, a), θ1 , . . . , θℓ−1 , Θ . The operator Tℓ is a γ-contraction, so Vℓ⋆ is its unique fixed point. The corresponding optimal action-value function is Q⋆ℓ (s, θ0 , . . . , θℓ−1 , a) := r(s, a) + γEΘ∼Q Vℓ⋆ θ0 (s, a), θ1 , . . . , θℓ−1 , Θ . An optimal policy is then obtained by choosing πℓ⋆ (s, θ0 , . . . , θℓ−1 ) ∈ arg maxa∈A Q⋆ℓ (s, θ0 , . . . , θℓ−1 , a).
3
H ARDNESS OF EXACT PLANNING
Our first result strengthens the known hardness of multi-step transition look-ahead planning of Pla et al. (2026a) by showing that it persists for every fixed discount factor. Analogously to the statevalue criterion in a standard MDP, we average over the look-ahead window revealed at the initial decision time and define vℓπ (s) := EC∼Q⊗ℓ [Vℓπ (s, C)], and vℓ⋆ (s) := EC∼Q⊗ℓ [Vℓ⋆ (s, C)]. Theorem 1 (Fixed-discount hardness of transition look-ahead planning). Fix an integer ℓ ≥ 2 and a rational discount factor γ ∈ (0, 1). Given a finite MDP M, an initial state s0 ∈ S, and a rational threshold θ, deciding whether there exists a policy with perfect ℓ-step transition look-ahead such that vℓπ (s0 ) ≥ θ is NP-hard.
Proof sketch. We adapt the hardness reduction of Pla et al. (2026a), which relies on the expectedmaximum gap construction of Mehta et al. (2020). The construction provides independent random variables X1 , . . . , Xn and an integer k for which it is hard to distinguish between the following two cases: either every subset Y ⊆ [n] of size k satisfies E [maxi∈Y Xi ] ≤ U, or there exists a subset Y ⋆ of size k such that E [maxi∈Y ⋆ Xi ] ≥ U + ∆, for some threshold U and gap ∆ > 0. The MDP reduction turns this construction into a planning problem. At the root state, the look-ahead reveals a random candidate subset Y of size at most k. The agent can either commit to this subset, in which case its value is γ ℓ+1 E [maxi∈Y Xi ] , or wait one step and observe a fresh independent candidate subset. Therefore, if every subset has expected maximum at most U , every commitment is worth at most T := γ ℓ+1 U. The difficulty is that a valuable subset may require many waiting steps before it appears, and its eventual gain is then strongly discounted unless γ is sufficiently close to one. Our modification removes this issue by assigning the waiting action the reward (1 − γ)T. This choice makes T a fixed point of waiting, since (1−γ)T +γT = T. Hence, when all candidate subsets have expected maximum at most U , committing gives at most T , while waiting also preserves an upper bound of T . The optimal value at the root is therefore at most T . On the other hand, if a subset Y ⋆ satisfies E [maxi∈Y ⋆ Xi ] ≥ U + ∆, then committing when Y ⋆ appears gives strictly more than T . The agent can repeatedly wait until this favorable subset is revealed and then commit. The waiting rewards preserve the baseline T , while only the positive surplus above T is discounted until the subset appears. Since the favorable subset occurs with positive probability at each fresh draw, this surplus remains strictly positive for every fixed γ ∈ (0, 1). Thus the two cases of the expected-maximum gap lead respectively to an optimal value at most T and strictly larger than T . This yields the desired hardness result for every fixed γ ∈ (0, 1), removing the requirement in Pla et al. (2026a) that γ be chosen sufficiently close to one. The full reduction and encoding argument are given in Appendix A.1.
4
N EAR OPTIMAL PLANNING
We now turn to our positive result: for every fixed look-ahead depth, near-optimal planning admits a randomized polynomial-time approximation scheme. 4
4.1
A LGORITHM
Our algorithm proceeds in two phases. Offline, it samples a finite collection of transition tables and uses them to build a finite state space, value iteration is then run once on this sampled state space. Online, the agent combines the precomputed values with the actual look-ahead window it observes in order to select an action. Algorithm 1 Offline Value Iteration Input: MDP M = (S, A, P, r), look-ahead depth ℓ, dictionary size N , iterations K Output: Policy representation D i.i.d. 1: Sample Θ1 , . . . , ΘN ∼ Q ℓ 2: Set CN ← S × [N ] 3: Initialize v 0 (s, i0 , . . . , iℓ−1 ) ← 0 for all (s, i0 , . . . , iℓ−1 ) ∈ CN 4: for k = 0, . . . , K − 1 do 5: for all (s, i0 , . . . , iℓ−1 ) ∈ CN do N γ X 6: v k+1 (s, i0 , . . . , iℓ−1 ) ← max{r(s, a) + v k Θi0 (s, a), i1 , . . . , iℓ−1 , j } a∈A N j=1 7: end for 8: end for 9: D ← (Θ1 , . . . , ΘN , v K ) 10: return D
(3)
Algorithm 2 Online Action Selection Input: D = (Θ1 , . . . , ΘN , V K ), current state s, observed window c = (θ0 , . . . , θℓ−1 ) Output: Action πD (s, c) VK 1: Uℓ,c (u, i0 , . . . , iℓ−1 ) ← V K (u, i0 , . . . , iℓ−1 ) for all (u, i0 , . . . , iℓ−1 ) ∈ CN 2: for k = ℓ − 1, . . . , 1 do 3: for all (u, i0 , . . . , ik−1 ) ∈ S × [N ]k do N K γ X VK 4: Uk,c (u, i0 , . . . , ik−1 ) ← max{r(u, a) + UV θk (u, a), i0 , . . . , ik } a∈A N ik =1 k+1,c 5: end for 6: end for 7: for all a ∈ A do N VK e V K (a) ← r(s, a) + γ X U1,c θ0 (s, a), i0 8: Q N i0 =1 9: end for e V K (a) 10: return πD (s, c) ← arg max Q a∈A
i.i.d.
Offline phase. Given N and K, sample a dictionary Θ1 , . . . , ΘN ∼ Q and define CN := S × [N ]ℓ , where (i0 , . . . , iℓ−1 ) ∈ [N ]ℓ represents the window (Θi0 , . . . , Θiℓ−1 ). Algorithm 1 runs K value-iteration steps on CN (as defined equation 3), obtaining V K : CN → [0, Vmax ], where Vmax = Rmax /(1 − γ). Hence, the offline output D = (Θ1 , . . . , ΘN , V K ) is computed once, without enumerating Ωℓ . Online phase. At decision time, the agent observes its current state s and a look-ahead window c = (θ0 , . . . , θℓ−1 ) ∈ Ωℓ . In general, the tables θ0 , . . . , θℓ−1 are different from those sampled offline, so V K cannot be evaluated directly on the observed window. Instead, Algorithm 2 connects the observed window to the values computed offline through a backward recursion. Starting from V K , the recursion processes the observed tables in reverse order. Initialize K
V Uℓ,c (u, i0 , . . . , iℓ−1 ) := V K (u, i0 , . . . , iℓ−1 ),
5
∀(u, i0 , ..., iℓ−1 ) ∈ CN
(4)
Then, for m = ℓ − 1, . . . , 1, define ( VK Um,c (u, i0 , . . . , im−1 ) := max a∈A
) N γ X VK r(u, a) + U θm (u, a), i0 , . . . , im . N i =1 m+1,c
(5)
m
At level m, the observed table θm determines the next state, while the transition table entering beyond the observed window is averaged over the N samples drawn offline. Proceeding backward in this way incorporates the entire observed look-ahead window into the precomputed values. Once θ1 , . . . , θℓ−1 have been processed, each action at the current state is assigned the score N X VK e V K (s, c, a) := r(s, a) + γ Q U1,c θ0 (s, a), i0 . N i =1
(6)
0
e V K (s, c, a). And the policy selects : πD (s, c) = arg maxa∈A Q 4.2
T HEORETICAL G UARANTEES
Theorem 2 (RPTAS for perfect transition look-ahead). Fix ℓ ≥ 2 and ε, δ ∈ (0, 1). For suitable choices of the sample size N and the number of value-iteration steps K, algorithm 1–2 described above computes a policy π such that P Vℓπ (s, c) ≥ Vℓ⋆ (s, c) − εVmax , ∀(s, c) ∈ S × Ωℓ ≥ 1 − δ. (7) For every fixed ℓ, computing and storing the policy, as well as selecting an action at each decision time, require time and memory polynomial in n, m, ε−1 , log(1/δ), and (1 − γ)−1 . Proof sketch. We first control the error introduced by replacing the true transition distribution with b N := 1 PN δΘj be the distribution supported on the sampled tranthe N sampled tables. Let Q j=1 N b ⋆ denote the optimal value and action-value functions obtained by sition tables, and let Vb ⋆ and Q b N . Since V ⋆ is fixed independently of the samples, Hoeffding’s inequality replacing Q with Q ℓ and a union bound over all states and look-ahead suffixes give, with probability at least 1 − δ, sup PN 1 ⋆ j ⋆ u∈S j=1 Vℓ (u, θ1:ℓ−1 , Θ ) − EΘ∼Q [Vℓ (u, θ1:ℓ−1 , Θ)] ≤ η. Then, usual contraction ℓ−1 N θ1:ℓ−1 ∈Ω
γη b ⋆ − Q⋆ ∥∞ ≤ γη . The important point is that this , and ∥Q argument yields ∥Vb ⋆ − Vℓ⋆ ∥∞ ≤ 1−γ ℓ 1−γ bound holds simultaneously for every possible look-ahead window.
b N and to The idea is to use the same sampled tables both to define the empirical distribution Q construct the finite state space CN . Consider the finite MDP induced by the dictionary, with state space CN . From a state (s, i0 , . . . , iℓ−1 ), taking action a yields reward r(s, a) and the next state s′ = Θi0 (s, a), (i1 , . . . , iℓ−1 , J), J ∼ Unif([N ]). This is exactly the dynamics of the augmented MDP b N : when the current window is (Θi0 , . . . , Θiℓ−1 ), the next table is uniformly distributed over under Q Θ1 , . . . , ΘN . Therefore, the finite MDP and the empirical augmented MDP have identical Bellman equations on dictionary windows. Their optimal values consequently satisfy VN⋆ (s, i0 , . . . , iℓ−1 ) = Vb ⋆ s, Θi0 , . . . , Θiℓ− , where VN∗ is the optimal value function on CN . Since Algorithm 1 performs only K value-iteration steps, sup V K (s, i0 , . . . , iℓ−1 ) − Vb ⋆ s, Θi0 , . . . , Θiℓ−1 ≤ γ K Vmax . s,i0 ,...,iℓ−1
Online, the observed window c = (θ0 , . . . , θℓ−1 ) need not belong to the dictionary. The online recursion does not approximate this window: it inserts its tables exactly, from θℓ−1 back to θ0 , and uses the dictionary only to average over the new table entering beyond the observed horizon. Starting from the exact offline value VN⋆ , backward induction gives V⋆ Uk,cN (u, i0 , . . . , ik−1 ) = Vb ⋆ u, θk , . . . , θℓ−1 , Θi0 , . . . , Θik−1 . 6
e V ⋆ (s, c, a) = Q b ⋆ (s, c, a). Using V K instead of V ⋆ introduces at most At the root, this yields Q N N K+ℓ γ Vmax error, since each of the ℓ online backups is γ-Lipschitz. Together with the sampling error, uniformly over all (s, c, a), e V K (s, c, a) − Q⋆ℓ (s, c, a) ≤ γη + γ K+ℓ Vmax . Q 1−γ l m 2 8 2 , and K = Set η = ε(1−γ)4 Vmax , N = ε2 (1−γ)4 log δ + 1 + (ℓ − 1)nm log n l m 1 4 1−γ log ε(1−γ) . The score error is then at most ε(1−γ)Vmax /2 simultaneously for every window. The preprocessing time, query time, and representation size are respectively O N nm + Kn(m + 1)N ℓ ,
O ℓn(m + 1)N ℓ ,
O N nm + nN ℓ + ℓnm ,
and are polynomial for fixed ℓ.
5
R EGRET MINIMIZATION
We now consider the online setting in which both the transition kernel P and the mean reward function r : S × A → [0, Rmax ] are initially unknown. At time t, the learner observes Xt = (St , Ctℓ ), chooses At , and receives a stochastic reward Rt ∈ [0, Rmax ] with conditional mean r(St , At ). We measure performance through the cumulative Bellman gap Regℓ (T ) := PT −1 ⋆ ⋆ t=0 [Vℓ (Xt ) − Qℓ (Xt , At )] . We introduce DLA-UCB (Dictionary Look-Ahead with Upper Confidence Bounds), an online extension of the planner from Section 4. At each update, the learner estimates the transition law from past tables, constructs optimistic reward estimates, samples a fresh dictionary from the estimated model, and solves the resulting finite MDP using an optimistic Bellman backup. At decision time, it applies the same backward recursion as before, with the observed look-ahead window and the optimistic backup. More precisely, from N past transition tables, the learner estimates each marginal P (· | s, a) and 1 MN i.i.d. b b forms the ∼ QN , M N = m corresponding product distribution QN . It then samples Z , . . . , Z l N ℓ (1−γ)3 , and runs optimistic value iteration on S × [MN ] . For any vector y = (y1 , . . . , yMN ) ∈ [0, Vmax ]MN , let y and s(y) denote its empirical mean and standard deviation, and define 2 UN (y) := min Vmax , y + 8Vmax αN ρN + max 7αN s(y), 49Vmax αN
.
(8)
In a Bellman update, yj is the value of the successor obtained by appending the jth dictionary table: yj = v Z i0 (s, a), i1 , . . . , iℓ−1 , j . Thus, UN (y) replaces the empirical average of the possible successor values by an optimistic, variance-adaptive estimate. The variance term provides a Bernstein-type transition bonus, the αN ρN term controls data-dependent continuation values, and the quadratic term preserves monotonicity. The optimistic Bellman operator is then D,+ (TN,r + v)(s, i0 , . . . , iℓ−1 ) ( +
:= max min Vmax , r (s, a) + γUN a∈A
i0
v Z (s, a), i1 , . . . , iℓ−1 , j
MN j=1
) .
(9)
l m 2 1 Starting from v 0 ≡ Vmax , DLA-UCB- UPDATE applies this operator KN = 1−γ log 2N 1−γ times. During interaction, the resulting value array is extended to each observed window using the same optimistic backup. The planner is recomputed only when the transition sample size or a reward count doubles; between updates, the dictionary and value array remain fixed. 7
Algorithm 3 DLA-UCB- UPDATE Input: Sample size N , past transition tables Θ0 , . . . , ΘN −1 , current reward bound r+ , horizon T , confidence level δ Output: D = (Z 1:MN , v KN , r+ , αN , ρN ) b N , αN , ρN , MN , and KN 1: Compute Q i.i.d. b 2: Sample Z 1 , . . . , Z MN ∼ Q N 0 3: Initialize v ≡ Vmax on S × [MN ]ℓ 4: for k = 0, . . . , KN − 1 do D,+ k 5: v k+1 ← TN,r +v 6: end for 7: return D = (Z 1:MN , v KN , r + , αN , ρN )
Algorithm 4 DLA-UCB- ONLINE Input: Horizon T , look-ahead depth ℓ, confidence level δ Output: Actions A0 , . . . , AT −1 1: Set r + (s, a) ← Rmax for every (s, a) and D ← ∅ 2: Observe X0 = (S0 , C0ℓ ) and play an arbitrary action A0 3: Observe R0 , update the reward statistics, and store Θ0 4: for t = 1, . . . , T − 1 do 5: Observe Xt = (St , Ctℓ ) 6: if D = ∅, t is a power of two, or a reward count reached a new power of two after time t − 1 then 7: Set N ← 2⌊log2 t⌋ 8: D ← DLA-UCB- UPDATE(N, Θ0:N −1 , r+ , T, δ) 9: end if e t (Xt , ·) from (Z 1:MN , v KN , r+ , αN , ρN ) using the online recursion 10: Compute Q e t (Xt , a) 11: Play At ∈ arg maxa∈A Q 12: Observe Rt , update the reward statistics, and store Θt 13: end for There are at most O(nm log T ) recomputations. One call to DLA-UCB- UPDATE costs ℓ ℓ ) per O KN n(m + 1)MN , while the online action-selection recursion costs O(ℓn(m + 1)MN −1 decision. Therefore, for fixed ℓ, both costs are polynomial in n, m, T , and (1 − γ) . Theorem 3 (Regret of DLA-UCB). Fix the look-ahead depth ℓ. For every T ≥ 2 and δ ∈ (0, 1), with probability at least 1 − δ, DLA-UCB satisfies s ! 2 nmT R n m max e Rmax Regℓ (T ) = O + . (10) 1−γ (1 − γ)2 The leading term matches, up to logarithmic factors, the optimal dependence on n, m, T , and (1 − γ)−1 obtained for classical tabular discounted MDPs (Liu & Su, 2021; He et al., 2022). Thus, despite the exponentially large augmented state space, transition look-ahead does not worsen the leading statistical dependence of the regret. The lower-order term comes from the uniform transition confidence bound required for the data-dependent optimistic value functions. Proof sketch. Fix a planner update based on N previously observed transition tables. The learner b N . This may still have first estimates each marginal P (· | s, a) and takes their product to obtain Q exponentially large support. To obtain a finite planning problem, DLA-UCB then draws an indei.i.d. b pendent dictionary Θ1 , . . . , ΘMN ∼ Q N . Thus, the transition approximation occurs in two steps: b N −→ {Θ1 , . . . , ΘMN }. The first step is a statistical estimation error, whereas the Q −→ Q second is the Monte Carlo error used to make planning computationally tractable. Statistical estimation error. First consider an ideal planner that uses the same bonuses as DLAb N . For any bounded function V : UCB, but computes expectations and variances exactly under Q 8
Ω → [0, Vmax ], define : UCBN (V ) n n oo q 2 Var (V (Θ)), 49V α := min Vmax , EΘ∼Q [V (Θ)] + 8V α ρ + max 7α . max N max N N N bN bN Q Now, fix c = (θ0 , . . . , θℓ−1 ) and a ∈ A, and let σQ and σ bN be the standard deviations, under Q and ⋆ b QN , of Vℓ (θ0 (s, a), θ1:ℓ−1 , Θ). The Bernstein bound gives 2 √ Vmax αN ⋆ 2αN σQ + . (11) EQ [Vℓ⋆ (θ0 (s, a), θ1:ℓ−1 , Θ)] ≤ EQ b N [Vℓ (θ0 (s, a), θ1:ℓ−1 , Θ)] + 3 And Hellinger bound gives σQ ≤ σ bN + 2Vmax ρN . The bonus in UCBN therefore dominates the preceding estimation error, so, uniformly over (s, c, a), UCBN (Vℓ⋆ (θ0 (s, a), θ1:ℓ−1 , ·)) ≥ EQ [Vℓ⋆ (θ0 (s, a), θ1:ℓ−1 , Θ)] . Since r+ ≥ r, the ideal Bellman operator satisfies T N,r+ Vℓ⋆ ≥ Tℓ Vℓ⋆ = Vℓ⋆ . Monotonicity and contraction then imply that its fixed point is optimistic: V N,r+ ≥ Vℓ⋆ . bN , Finite-dictionary approximation. The ideal planner averages over all transition tables under Q 1 MN i.i.d. b whose support may be exponentially large. Θ ,...,Θ ∼ QN DLA-UCB instead samples by the dictionary average and replaces each expectation EΘ∼Q b N V N,r + θ0 (s, a), θ1:ℓ−1 , Θ PMN 1 j j=1 V N,r + θ0 (s, a), θ1:ℓ−1 , Θ , and similarly replaces the corresponding standard deviaMN b N and V N,r+ are fixed. Standard tion by its empirical counterpart. Conditionally on the past data, Q concentration therefore shows that replacing the exact mean and standard deviation by their dictioq nm e nary estimates changes one Bellman backup by at most O Vmax MN uniformly over all states and look-ahead suffixes. Since both Bellman operators are γ-contractions, their fixed points differ by KN at most this one-step error divided by 1 − γ. Stopping value m after KN stepsladds γ Vmax m, l iteration q V nm 1 2N 2 N K D max N eℓ and K = log + γ V . With M = so εN ≤ O N max N 1−γ MN (1−γ)3 1−γ 1−γ , this becomes e εD N = Oℓ
r Rmax
Rmax nm + N (1 − γ) N2
.
As in the planning analysis, the online recursion inserts the observed tables exactly and uses the same backup as the finite Bellman operator. It therefore introduces no new approximation, and e N,r+ (s, c, a) − QN,r+ (s, c, a) ≤ εD sup Q N.
s,c,a
Regret bound. Let ∆t (x) := V Nt ,r+ (x) − Vℓ⋆ (x) ≥ 0 denote the optimism gap of the ideal planner t active at time t. Approximate greediness and the optimistic Bellman equation bound the instantaneous Bellman gap by the reward-estimation error, the dictionary error, the transition-confidence width, and γE[∆t (Xt+1 ) | Ft ] − ∆t (Xt ). The last two terms do not accumulate over time. Indeed, if the planner remains unchanged between times p and q, replacing conditional expectations by realized values gives q X
[γ∆t (Xt+1 ) − ∆t (Xt )] = −∆p (Xp ) + γ∆p (Xq+1 ) − (1 − γ)
t=p
q X
∆p (Xt ).
t=p+1
A predictable-to-realized concentration argument justifies this replacement. Since 0 ≤ ∆p ≤ Vmax , the boundary terms cost at most Vmax per planner update, while the negative sum absorbs the part of the transition width depending on the optimism gap. Summing the remaining reward, dictionary, and confidence terms with the doubling schedule gives s ! X nmT Rmax n2 m e Regℓ (T ) ≤ Oℓ Rmax + + C γαt σt , 1−γ (1 − γ)2 t<T
9
where σt2 = Var(Vℓ⋆ (Xt+1 ) | Ft ). It remains to control this Bernstein term. The Bellman equation and Freedman’s inequality imply X 2 γ 2 σt2 ≲ Vmax Rmax T + Vmax Regℓ (T ) + Vmax log(1/δ). t<T
Together with
2 e t<T αt = Oℓ (nm), Cauchy–Schwarz yields
P
s X t<T
eℓ γαt σt = O
Rmax
! p nmT + nmVmax Regℓ (T ) . 1−γ
Young’s inequality absorbs the last term into the regret itself, giving s ! nmT Rmax n2 m e Regℓ (T ) = Oℓ Rmax . + 1−γ (1 − γ)2
6
C ONCLUSION
We studied the computational complexity of planning with multi-step transition look-ahead in discounted MDPs. We first showed that exact planning remains NP-hard for every fixed rational discount factor and every fixed look-ahead horizon ℓ ≥ 2. Despite this hardness, we proved that near-optimal planning is computationally tractable: for every fixed ℓ, our randomized approximation scheme constructs, with high probability, a uniformly near-optimal policy in polynomial time and memory. The key algorithmic idea is to replace the distribution of transition realizations by a finite dictionary of complete transition tables, solve the resulting empirical Bellman problem on a finite core, and extend the resulting value function to arbitrary observed look-ahead windows at deployment. These results show that the exponential augmented state space induced by transition look-ahead does not by itself preclude efficient approximate control. An interesting direction for future work is to determine whether similar approximation guarantees can be obtained when the look-ahead depth is part of the input, or under imperfect, dependent, or partially observed transition predictions.
R EFERENCES Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International conference on machine learning, pp. 263–272. PMLR, 2017. Nikhil Balaji, Stefan Kiefer, Petr Novotnỳ, Guillermo A Pérez, and Mahsa Shirmohammadi. On the complexity of value iteration. arXiv preprint arXiv:1807.04920, 2018. Ziyad Benomar and Vianney Perchet. On tradeoffs in learning-augmented algorithms. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan (eds.), Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 802–810. PMLR, 03–05 May 2025. URL https://proceedings. mlr.press/v258/benomar25a.html. Ziyad Benomar, Lorenzo Croissant, Vianney Perchet, and Spyros Angelopoulos. Pareto-optimality, smoothness, and stochasticity in learning-augmented one-max-search. In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum? id=ZTOVlPC5Vf. Yichen Chen and Mengdi Wang. Lower bound on the computational complexity of discounted markov decision problems, 2017. URL https://arxiv.org/abs/1705.07312. Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps, 2022. URL https://arxiv.org/abs/2010.00587. Thomas Jaksch, Rudolf Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. In Journal of Machine Learning Research, volume 11, pp. 1563–1600, 2010. 10
Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael I. Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pp. 4863– 4873, 2018. Michael Kearns, Yishay Mansour, and Andrew Y. Ng. A sparse sampling algorithm for near-optimal planning in large markov decision processes. Machine Learning, 49(2–3):193–208, 2002. doi: 10.1023/A:1017932429737. Anton J. Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2):479–502, 2002. doi: 10.1137/S1052623499363220. Tongxin Li, Yiheng Lin, Shaolei Ren, and Adam Wierman. Beyond black-box advice: Learningaugmented algorithms for MDPs with q-value predictions. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreview.net/forum?id= RACcp8Zbr9. Tongxin Li, Hao Liu, and Yisong Yue. Disentangling linear quadratic control with untrusted ml predictions. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 86860–86898. Curran Associates, Inc., 2024. URL https://proceedings.neurips.cc/paper_files/paper/2024/file/ 9dff3b83d463fab213941bfee23341ba-Paper-Conference.pdf. Michael L. Littman, Thomas L. Dean, and Leslie Pack Kaelbling. On the complexity of solving markov decision problems, 2013. URL https://arxiv.org/abs/1302.4971. Shuang Liu and Hao Su. Regret bounds for discounted mdps, 2021. URL https://arxiv. org/abs/2002.05138. Chenbei Lu, Zaiwei Chen, Tongxin Li, Chenye Wu, and Adam Wierman. Reinforcement learning with imperfect transition predictions: A bellman-jensen approach. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https://openreview. net/forum?id=DYuPwwDy9n. Lixing Lyu, Jiashuo Jiang, and Wang Chi Cheung. Efficiently solving discounted MDPs via predictions with unknown prediction errors. In Forty-third International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=0nrxgFZEEq. Davide Maran, Davide Salaorni, and Marcello Restelli. Learning in markov decision processes with exogenous dynamics, 2026. URL https://arxiv.org/abs/2603.02862. Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization, 2009. URL https://arxiv.org/abs/0907.3740. Aranyak Mehta, Uri Nadav, Alexandros Psomas, and Aviad Rubinstein. Hitting the high notes: Subset selection for maximizing expected order statistics. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15800–15810. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/ file/b6417f112bd27848533e54885b66c288-Paper.pdf. Nadav Merlis. Reinforcement learning with lookahead information. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview. net/forum?id=wlqfOvlTQz. Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, and Vianney Perchet. On preemption and learning in stochastic scheduling. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 24478–24516. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/v202/merlis23a.html. 11
Nadav Merlis, Dorian Baudry, and Vianney Perchet. The value of reward lookahead in reinforcement learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://arxiv.org/abs/2403.11637. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions, 2020. URL https: //arxiv.org/abs/2006.09123. Martin Mundhenk, Judy Goldsmith, Christopher Lusena, and Eric Allender. Complexity of finitehorizon markov decision process problems. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI), pp. 494–499, 2000. C. H. Papadimitriou. The complexity of markov decision processes. Mathematics of Operations Research, 12(3):441–450, 1987. Corentin Pla, Hugo Richard, Marc Abeille, Nadav Merlis, and Vianney Perchet. On the hardness of reinforcement learning with transition lookahead. In The 29th International Conference on Artificial Intelligence and Statistics, 2026a. URL https://openreview.net/forum?id= clyOoEL3pS. Corentin Pla, Hugo Richard, Marc Abeille, and Vianney Perchet. Minimax pac bounds for learning in exogenous contextual mdps, 2026b. URL https://arxiv.org/abs/2606.25170. Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Hoboken, NJ, 2nd edition, 2014. Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 2nd edition, 2018. Shoshana Vasserman, Michal Feldman, and Avinatan Hassidim. Implementing the wisdom of waze. In IJCAI, volume 15, pp. 660–666, 2015. Thomas J. Walsh, Ali Nouri, Lihong Li, and Michael L. Littman. Learning and planning in environments with delayed feedback. Autonomous Agents and Multi-Agent Systems, 18(1):83–105, 2009. doi: 10.1007/s10458-008-9056-7.
A
A PPENDIX
A.1
P ROOF OF T HEOREM 1
We use the notation of Section 2: Ω = S S×A is the space of one-step transition tables, Q is the product law equation 1 induced by the kernel P , and Vℓ⋆ denotes the optimal value function on the augmented state space S × Ωℓ . For a policy π and an initial state s0 ∈ S, define the values averaged over the initial look-ahead window, π ⋆ vℓ,γ (s0 ) := EC∼Q⊗ℓ Vℓπ (s0 , C) , vℓ,γ (s0 ) := EC∼Q⊗ℓ Vℓ⋆ (s0 , C) , (12) π so that vℓ,γ (s0 ) is the quantity appearing in the statement of Theorem 1. For a window c = (θ0 , . . . , θℓ−1 ) ∈ Ωℓ , a state s ∈ S, and an action sequence σ = (a0 , . . . , ak−1 ) with k ≤ ℓ, we write ϕc (s, σ) ∈ S for the state reached after playing σ from s under the window c, that is, the state sk obtained from the recursion
s0 = s,
sj+1 = θj (sj , aj ),
j = 0, . . . , k − 1.
Definition 2 (ℓ-DVDP). Given a finite MDP M = (S, A, P, r), a rational discount factor γ ∈ (0, 1), an initial state s0 ∈ S, and a rational threshold θ, decide whether there exists a policy π with π ⋆ ℓ-step transition look-ahead such that vℓ,γ (s0 ) ≥ θ, equivalently whether vℓ,γ (s0 ) ≥ θ. Fix an integer ℓ ≥ 2 and a rational discount factor γ ∈ (0, 1). We build upon Pla et al. (2026a) and exhibit a polynomial-time reduction from I NDEPENDENT S ET on regular graphs to ℓ-DVDP that is valid for this fixed γ; NP-hardness is therefore preserved even for γ far from 1. We use the following consequence of the reduction of Mehta et al. (2020); it is the same gap gadget as in the hardness proof of Pla et al. (2026a). The graph parameters are denoted nG and mG . 12
Lemma 1 (Expected-maximum gap). There is a polynomial-time reduction that maps an instance (G, k) of I NDEPENDENT S ET on a regular graph G = (V, E), with nG = |V | and mG = |E|, to mutually independent, nonnegative, finite-support random variables (Xv )v∈V with rational values and probabilities of polynomial encoding length. All variables have the same expectation µ, and the following hold: 1. If G contains an independent set S ⋆ of size k, then 2 E max⋆ Xv ≥ kµ − . v∈S mG 2. If G contains no independent set of size k, then every S ⊆ V with |S| = k satisfies E max Xv ≤ kµ − 1. v∈S
We may assume without loss of generality that mG ≥ 3: instances with at most two edges can be decided in polynomial time. Set 2 ∆ := 1 − > 0. mG Define B := kµ − 1, L := 1 + max{0, −B}, U := L + B. Then U ≥ 1. Shift every random variable by the same deterministic amount: Yv := Xv + L. For every nonempty S ⊆ V , E max Yv = L + E max Xv . v∈S
Consequently, Lemma 1 becomes NO case: E max Yv ≤ U v∈S YES case: E max⋆ Yv ≥ U + ∆ v∈S
v∈S
for every S ⊆ V, |S| = k,
(13)
for some independent set S ⋆ , |S ⋆ | = k.
(14)
The shift is used only to ensure that all rewards introduced below are nonnegative. MDP construction.
For each v ∈ V , write the finite support of Yv as supp(Yv ) = {yv,1 , . . . , yv,Nv },
P(Yv = yv,h ) = pv,h .
The state space of the MDP MG is S = {s0 , s1 , sT } ∪ {d1 , . . . , dℓ−2 } ∪ {sv : v ∈ V } ∪ {xv,h : v ∈ V, h ∈ [Nv ]}.
(15)
The delay states d1 , . . . , dℓ−2 are absent when ℓ = 2. The action set is A = {wait, go, advance, claim, collect} ∪ {pick1 , . . . , pickk }. Set
T := γ ℓ+1 U,
b := (1 − γ)T.
The only nonzero rewards are r(s0 , wait) = b,
r(xv,h , collect) = yv,h .
All rewards are nonnegative and bounded by Rmax := maxv,h yv,h . The transition kernel is as follows. 13
(16)
(17)
1. At the root s0 , P (s0 | s0 , wait) = 1. If ℓ = 2, action go moves deterministically to s1 ; if ℓ ≥ 3, it moves deterministically to d1 . 2. At a delay state di , action advance moves deterministically to di+1 when i < ℓ − 2, and from dℓ−2 to s1 . 3. At the selector state s1 , each action pickj , j ∈ [k], has the uniform transition law P (sv | s1 , pickj ) =
1 , nG
v ∈ V.
(18)
4. At a vertex state sv , action claim samples the corresponding payoff state: P (xv,h | sv , claim) = pv,h ,
h ∈ [Nv ].
5. At a payoff state xv,h , action collect moves deterministically to sT . 6. The terminal state sT is absorbing. Every action not explicitly specified above moves deterministically to sT and gives reward zero. Candidate tuples and the value of committing. We call root augmented state any augmented state of the form (s0 , c) with c = (θ0 , . . . , θℓ−1 ) ∈ Ωℓ . For j ∈ [k], define the length-ℓ action sequence (19) σj := (go, advance, . . . , advance, pickj ), {z } | ℓ−2 times
with the obvious interpretation (go, pickj ) when ℓ = 2. The first ℓ−1 actions of σj deterministically drive the system from s0 to s1 , so there is a unique qj (c) ∈ V such that ϕc (s0 , σj ) = sqj (c) ,
namely sqj (c) = θℓ−1 (s1 , pickj ).
Write q(c) := (q1 (c), . . . , qk (c)) ∈ V k ,
S(c) := {q1 (c), . . . , qk (c)}.
(20)
⊗ℓ
When C ∼ Q , the coordinates of q(C) are independent and uniform on V , because they arise from the distinct state–action pairs (s1 , pickj ) of a single product-distributed table, via equation 18. Lemma 2 (Commit value and root recursion). For every root augmented state (s0 , c), the value obtained by choosing go at (s0 , c) and then acting optimally is ℓ+1 C(c) = γ E max Yv . (21) v∈S(c)
Moreover, Vℓ⋆ (s0 , c) = max {C(c), b + γ E[Vℓ⋆ (s0 , C ′ ) | c, wait]} ,
(22)
where C ′ = (θ1 , . . . , θℓ−1 , Θ) with Θ ∼ Q independent of the past. Finally, after playing wait, the next candidate tuple q(C ′ ) is an independent fresh draw from the uniform distribution on V k . Proof. After go, the process traverses the deterministic delay chain and cannot return to s0 . There are no rewards on this part of the trajectory. The system reaches s1 exactly ℓ − 1 steps after leaving s0 . At that time, the current ℓ-step look-ahead window contains, for every j ∈ [k], both sqj (c)
and
xqj (c),hj
along the continuation (pickj , claim), since ℓ ≥ 2. Hence the realization of Yqj (c) is known before the action pickj is selected. Note also that, by prefix consistency of the look-ahead windows, the vertex reached under pickj at that time is exactly qj (c): the transition (s1 , pickj ) is governed by the last table of the root window, which is also the table governing the system when it actually reaches s1 . For distinct vertices, these payoff samples are independent; if the same vertex appears several times in q(c), prefix consistency makes the corresponding branches share the same sample from the pair (sv , claim). Therefore the selector obtains the largest realized value among the distinct variables indexed by S(c). 14
Moreover, the payoff realizations are not observable at the root: the payoff states xv,h lie at depth ℓ+1 from s0 under (σj , claim), one level beyond the depth-ℓ tree revealed by c. Hence, conditionally on the root window, the variables (Yv )v∈S(c) have their unconditional product law. Starting from s1 , the reward is collected two steps later: one transition under pickj , one under claim, and then the immediate reward of collect at the payoff state. The conditional value at s1 is thus γ 2 max Yv . v∈S(c)
The selector is reached ℓ − 1 steps after leaving s0 , so the value at the root is ℓ−1 2 ℓ+1 γ E γ max Yv = γ E max Yv , v∈S(c)
v∈S(c)
which proves equation 21. At s0 , the only potentially optimal actions are go and wait, since every other action leads to the absorbing state sT with zero reward. The former has value C(c). The latter gives immediate reward b, returns to s0 , and then has continuation value γ E[Vℓ⋆ (s0 , C ′ ) | c, wait]. This proves equation 22. Finally, after wait, the candidate transitions lie one level beyond the old look-ahead tree: q(C ′ ) is determined by the entries (s1 , pickj ) of the newly revealed table Θ, which is independent of all previously observed tables. The augmented transition kernel therefore samples them independently from equation 18, independently of the previous tuple. Hence q(C ′ ) is a fresh uniform draw from V k . In particular, the current window never reveals the next candidate tuple before wait is played.
Proof of Theorem 1. We show that the map (G, k) 7→ (MG , s0 , γ, θ), with θ defined in equation 30 below, is a valid many-one reduction from I NDEPENDENT S ET to ℓ-DVDP. Soundness. Assume that G is a NO instance of I NDEPENDENT S ET. Fix a root window c ∈ Ωℓ . The set S(c) may contain fewer than k vertices because the tuple can have repetitions. Extend it to any set Se ⊇ S(c) of cardinality k. Since the expected maximum is monotone under set inclusion (the Yv are nonnegative), equation 13 gives E max Yv ≤ E max Yv ≤ U. (23) v∈S(c)
e v∈S
By equation 21 and equation 17, C(c) ≤ γ ℓ+1 U = T.
(24)
Let M := max{Vℓ⋆ (s0 , c) : c ∈ Ωℓ }. The set Ωℓ is finite, so the maximum exists. From Lemma 2 and equation 24, M ≤ max{T, b + γM }. If M > T , then necessarily M ≤ b + γM = (1 − γ)T + γM, which implies (1 − γ)M ≤ (1 − γ)T , contradicting M > T . Therefore M ≤ T.
(25)
In particular, after averaging over the initial root window, ⋆ vℓ,γ (s0 ) ≤ T.
15
(26)
Completeness.
Assume that G is a YES instance, and let S ⋆ = {v1 , . . . , vk }
be an independent set satisfying equation 14. Consider the following stationary policy on the augmented state space: • at a root augmented state (s0 , c), choose go if q(c) = (v1 , . . . , vk ), and choose wait otherwise; • traverse the deterministic delay chain using advance; • at s1 , choose an index whose revealed payoff is maximal; • use claim and then collect. This policy is well defined: the tuple q(c) is observable at the root, and the realized payoffs are observable at s1 , by Lemma 2. At every visit to s0 , the target tuple appears with probability ρ := n−k G .
(27)
By the last part of Lemma 2, successive tuples are independent. Let τ ∈ {0, 1, 2, . . .} be the number of waiting actions before the target tuple first appears. Then P(τ = t) = (1 − ρ)t ρ, and therefore τ
α := E[γ ] =
∞ X
ρ(1 − ρ)t γ t =
t=0
ρ . 1 − γ(1 − ρ)
(28)
The discounted return of this policy is τ −1 X
γ t b + γ τ +ℓ+1 max⋆ Yv . v∈S
t=0
The payoff samples generated after commitment are independent of the waiting time (they are drawn from table entries never used to define the tuples) and have the laws (Yv )v∈S ⋆ , with all vertices of the target tuple distinct. Taking expectations and using b/(1 − γ) = T gives π vℓ,γ (s0 ) = T 1 − E[γ τ ] + E[γ τ ] γ ℓ+1 E max⋆ Yv v∈S = T + α γ ℓ+1 E max⋆ Yv − T v∈S
≥ T + αγ
ℓ+1
∆,
(29)
where the last inequality follows from equation 14 and T = γ ℓ+1 U . Decision threshold and polynomial encoding.
Define
1 θ := T + αγ ℓ+1 ∆. (30) 2 Because γ > 0, ρ > 0, and ∆ > 0, the added term is strictly positive. Equations equation 26 and equation 29 imply G is a NO instance
=⇒
⋆ vℓ,γ (s0 ) ≤ T < θ,
G is a YES instance
=⇒
⋆ vℓ,γ (s0 ) ≥ T + αγ ℓ+1 ∆ > θ.
Thus (G, k) 7→ (MG , s0 , γ, θ) is a valid many-one reduction to ℓ-DVDP. 16
It remains to verify polynomial size. The stochastic gadget in Lemma 1 has polynomially many support points and polynomial-bit rational values and probabilities. The MDP has ! X O nG + Nv + ℓ v∈V
states and k + 5 actions. Since ℓ is fixed, this is polynomial. The shift L, the quantities U, T, b, ∆, and the threshold θ are obtained by a constant number of rational arithmetic operations. Moreover, ρ = n−k G has encoding length O(k log nG ), and equation 28 therefore has polynomial encoding length. For fixed rational γ, its encoding length is constant; if γ is supplied in binary, all constructed numbers still have encoding length polynomial in the combined input size. This completes the reduction and the proof. A.2
P ROOF OF T HEOREM 2
We use the notation of Section 2: Ω = S S×A , Q is the law equation 1 on Ω, Tℓ is the Bellman optimality operator of the augmented MDP, and Vℓ⋆ , Q⋆ℓ are the optimal value and action-value max functions on S × Ωℓ . We write n = |S|, m = |A|, and Vmax := R1−γ , so that all value functions considered below take values in [0, Vmax ]. For windows we use the shorthand θk:k′ = (θk , . . . , θk′ ). We begin by defining the ideal empirical model. This model replaces the unknown expectation under Q with an average over a sampled dictionary, while retaining the same augmented state space as the true Bellman equation. Sample once and for all, independently, i.i.d.
Θ1 , . . . , ΘN ∼ Q,
(31)
N X b N := 1 δ j. Q N j=1 Θ
(32)
and set the empirical distribution
The associated empirical Bellman operator is N n o γ X (Tbℓ V )(s, θ0 , . . . , θℓ−1 ) := max r(s, a) + V θ0 (s, a), θ1 , . . . , θℓ−1 , Θj . a∈A N j=1
(33)
It is a γ-contraction for the sup norm on S × Ωℓ ; we denote by Vb ⋆ its unique fixed point, and define the empirical action scores Q⋆ℓ (s, θ0:ℓ−1 , a) = r(s, a) + γ EΘ∼Q Vℓ⋆ θ0 (s, a), θ1:ℓ−1 , Θ , (34) N X b ⋆ (s, θ0:ℓ−1 , a) := r(s, a) + γ Q Vb ⋆ θ0 (s, a), θ1:ℓ−1 , Θj , N j=1
(35)
where equation 34 simply restates the definition of Q⋆ℓ from Section 2. We now compare the ideal empirical model with the true model. Consider the function class F := θ 7→ Vℓ⋆ (u, θ1:ℓ−1 , θ) : u ∈ S, θ1:ℓ−1 ∈ Ωℓ−1 , (36) whose cardinality is at most |F | ≤ n|Ω|ℓ−1 = n1+(ℓ−1)nm , crucially, log |F| is therefore polynomial in n, m for fixed ℓ. Lemma 3 (Uniform concentration). For every η > 0, ! N 1 X ⋆ j ⋆ P sup Vℓ (u, θ1:ℓ−1 , Θ ) − EΘ∼Q [Vℓ (u, θ1:ℓ−1 , Θ)] > η u,θ1:ℓ−1 N j=1 2N η 2 ℓ−1 ≤ 2n|Ω| exp − 2 . (37) Vmax Proof. The function Vℓ⋆ is deterministic and does not depend on the sampled dictionary, so each function in F is fixed and takes values in [0, Vmax ]. We apply Hoeffding’s inequality to each function of F and then take a union bound. 17
Denote the event N X 1 Eη := sup Vℓ⋆ (u, θ1:ℓ−1 , Θj ) − EΘ∼Q [Vℓ⋆ (u, θ1:ℓ−1 , Θ)] ≤ η . u,θ1:ℓ−1 N j=1
Lemma 4 (Fixed-point stability). Under the event Eη , ∥Vb ⋆ − Vℓ⋆ ∥∞ ≤
γη . 1−γ
(38)
Proof. Fix (s, θ0:ℓ−1 ). For every a ∈ A, the bracketed terms in Tbℓ Vℓ⋆ and Tℓ Vℓ⋆ share the reward r(s, a) and differ by γ times an empirical-versus-true average of Vℓ⋆ (θ0 (s, a), θ1:ℓ−1 , ·), which is at most γη in absolute value on Eη . Since the maximum over a is 1-Lipschitz, ∥Tbℓ Vℓ⋆ − Tℓ Vℓ⋆ ∥∞ ≤ γη.
(39)
As Vℓ⋆ = Tℓ Vℓ⋆ , Vb ⋆ = Tbℓ Vb ⋆ , and Tbℓ is a γ-contraction, ∥Vb ⋆ − Vℓ⋆ ∥∞ ≤ ∥Tbℓ Vb ⋆ − Tbℓ Vℓ⋆ ∥∞ + ∥Tbℓ Vℓ⋆ − Tℓ Vℓ⋆ ∥∞ ≤ γ∥Vb ⋆ − V ⋆ ∥∞ + γη, ℓ
and rearranging proves the claim. Lemma 5. On Eη , sup s,θ0:ℓ−1 ,a
b ⋆ (s, θ0:ℓ−1 , a) − Q⋆ℓ (s, θ0:ℓ−1 , a)| ≤ |Q
γη . 1−γ
(40)
Proof. By adding and subtracting the empirical average of Vℓ⋆ , b ⋆ (s, θ0:ℓ−1 , a) − Q⋆ℓ (s, θ0:ℓ−1 , a)| |Q N
γ X b⋆ V θ0 (s, a), θ1:ℓ−1 , Θj − Vℓ⋆ θ0 (s, a), θ1:ℓ−1 , Θj + γη ≤ N j=1 ≤ γ∥Vb ⋆ − Vℓ⋆ ∥∞ + γη γη ≤ , 1−γ γη γη where the last step uses Lemma 4 and the identity γ 1−γ + γη = 1−γ .
The previous paragraph shows that Vb ⋆ is close to Vℓ⋆ , but Vb ⋆ is still formally defined on S × Ωℓ . We now show that windows composed only of tables from the dictionary equation 31 form a finite state space that is preserved by the empirical Bellman operator. Set DN := S × [N ]ℓ .
[N ] := {1, . . . , N },
(41)
For each i ∈ [N ], the index i refers to the sampled transition table Θi of the dictionary. Consequently, an index tuple i = (i0 , . . . , iℓ−1 ) ∈ [N ]ℓ encodes the window of transition tables (Θi0 , . . . , Θiℓ−1 ) ∈ Ωℓ ; the index ik specifies the dictionary table used at temporal level k of the look-ahead window. Define, on functions V : DN → R, N X γ (TbDN V )(s, i0 , . . . , iℓ−1 ) := max r(s, a) + V Θi0 (s, a), i1 , . . . , iℓ−1 , j . (42) a∈A N j=1
This operator is a γ-contraction; let VbD⋆N denote its unique fixed point. Lemma 6 (Exact restriction to the dictionary). For every (s, i0 , . . . , iℓ−1 ) ∈ DN , VbD⋆N (s, Θi0 , . . . , Θiℓ−1 ) = Vb ⋆ (s, Θi0 , . . . , Θiℓ−1 ). 18
(43)
Proof. For a function V : S × Ωℓ → R, denote RDN V its restriction to the dictionary DN Let (s, i0 , . . . , iℓ−1 ) ∈ DN (RDN Tbℓ V )(s, Θi0 , . . . , Θiℓ−1 ) = (Tbℓ V )(s, Θi0 , . . . , Θiℓ−1 ) N γ X = max r(s, a) + V Θi0 (s, a), Θi1 , . . . , Θiℓ−1 , Θj a∈A N j=1 N X γ = max r(s, a) + (RDN V ) Θi0 (s, a), Θi1 , . . . , Θiℓ−1 , Θj a∈A N j=1 = (TbDN RDN V )(s, Θi0 (s, a), Θi1 , . . . , Θiℓ−1 ), Now, since Tbℓ Vb ⋆ = Vb ⋆ , we obtain TbD (RN Vb ⋆ ) = RN (Tbℓ Vb ⋆ ) = RN Vb ⋆ . N
Thus RN Vb ⋆ is a fixed point of TbDN . Since TbDN is a γ-contraction, this fixed point is unique and therefore RN Vb ⋆ = VbD⋆N . Which gives equation 43. Remark 1 (Compute and memory cost of one interation.). For a function v : DN → R and every tuple (u, i1 , . . . , iℓ−1 ) ∈ S × [N ]ℓ−1 we compute N
Meanv (u, i1 , . . . , iℓ−1 ) =
1 X v(u, i1 , . . . , iℓ−1 , j). N j=1
(44)
Computing all the Meanv costs O(nN ℓ ); then computing all the maxima costs O(nmN ℓ ). All in all, one iteration of equation 42 costs O n(m + 1)N ℓ . (45) The operator TbDN is a γ-contraction on the finite dictionary DN and, therefore, can be solved by exact value iteration: V 0 = 0, V k+1 = TbDN V k . (46) VbD⋆N can only be evaluated on windows whose tables all belong to the sampled dictionary DN . However, the look-ahead window observed during deployment contains arbitrary tables, and therefore need not belong to the dictionary. To evaluate an arbitrary observed window c = (θ0 , . . . , θℓ−1 ), we work backward from VbD⋆N defined on dictionary windows, then, the recursion successively reintroduces the observed tables θℓ−1 , . . . , θ0 . We show below that, when initialized with the exact dictionary fixed point v ⋆ , this procedure returns exactly Vb ⋆ (s, c). v Formally, let c = (θ0 , . . . , θℓ−1 ) ∈ Ωℓ be an arbitrary window. Define the functions Uk,c by backward recursion. At the terminal level, Uℓ,c (s, i0 , . . . , iℓ−1 ) := VbD⋆ (s, i0 , . . . , iℓ−1 ). (47) N
For k = ℓ − 1, . . . , 1, ) N γ X Uk+1,c θk (s, a), i0 , . . . , ik . Uk,c (s, i0 , . . . , ik−1 ) := max r(s, a) + a∈A N i =1 (
(48)
k
Then, for every root action, define N X e θ0:ℓ−1 , a) := r(s, a) + γ Q(s, U1,c θ0 (s, a), i0 , N i =1 0 n o e θ0:ℓ−1 , a) . so that U0,c (s) := maxa∈A Q(s,
19
(49)
Lemma 7 (Exact extension identity). For every (s, θ0:ℓ−1 , a) ∈ S × Ωℓ × A, e ( s, θ0:ℓ−1 , a) = Q b ⋆ (s, θ0:ℓ−1 , a). Q
(50)
Proof. Fix an arbitrary window c = (θ0 , . . . , θℓ−1 ) ∈ Ωℓ . We first establish the intermediate identity v⋆ Uk,c (u, i0 , . . . , ik−1 ) = Vb ⋆ u, θk , . . . , θℓ−1 , Θi0 , . . . , Θik−1 (51) for every k ∈ {1, . . . , ℓ}, by backward induction on k. For k = ℓ, the terminal condition equation 47 and Lemma 6 give Uℓ,c (u, i0 , . . . , iℓ−1 ) = VbD⋆N (u, i0 , . . . , iℓ−1 ) = Vb ⋆ u, Θi0 , . . . , Θiℓ−1 , which is precisely equation 51 at level ℓ. Now suppose that equation 51 holds at level k + 1, for some k ∈ {1, . . . , ℓ − 1}. By equation 48 and the induction hypothesis, Uk,c (u, i0 , . . . , ik−1 ) ( ) N γ X = max r(u, b) + Uk+1,c θk (u, b), i0 , . . . , ik b∈A N i =1 k ( ) N γ X b⋆ i0 ik = max r(u, b) + V θk (u, b), θk+1 , . . . , θℓ−1 , Θ , . . . , Θ b∈A N i =1 k = (Tbℓ Vb ⋆ ) u, θk , . . . , θℓ−1 , Θi0 , . . . , Θik−1 = Vb ⋆ u, θk , . . . , θℓ−1 , Θi0 , . . . , Θik−1 , where the last equality uses Tbℓ Vb ⋆ = Vb ⋆ . This proves equation 51 for every k ∈ {1, . . . , ℓ}. Finally, fix the root action a. Applying the identity at level k = 1 in the definition equation 49 yields N X e θ0:ℓ−1 , a) = r(s, a) + γ U1,c θ0 (s, a), i0 Q(s, N i =1 0
= r(s, a) +
N γ X
N i =1
Vb ⋆ θ0 (s, a), θ1 , . . . , θℓ−1 , Θi0
0
b ⋆ (s, θ0:ℓ−1 , a), =Q where the last equality is the definition equation 35. Lemma 8 (Stability of the extension). For all arrays v1 , v2 : CN → [0, Vmax ] and every k ∈ {0, . . . , ℓ}, sup c,s,i0 ,...,ik−1
v1 v2 Uk,c (s, i0 , . . . , ik−1 ) − Uk,c (s, i0 , . . . , ik−1 ) ≤ γ ℓ−k ∥v1 − v2 ∥∞ .
(52)
Consequently, v1 v2 sup |U0,c (s) − U0,c (s)| ≤ γ ℓ ∥v1 − v2 ∥∞ ,
(53)
e v (s, c, a) − Q e v (s, c, a)| ≤ γ ℓ ∥v1 − v2 ∥∞ . sup |Q 1 2
(54)
s,c
s,c,a
Proof. Backward induction on k, the window c = (θ0 , . . . , θℓ−1 ) being fixed throughout since equation 48 never modifies it. v1 v2 For k = ℓ, the terminal condition equation 47 gives Uℓ,c − Uℓ,c = v1 − v2 , whose arguments range over exactly CN , so equation 52 holds with equality.
20
Assume equation 52 at level k + 1 and fix s, i0 , . . . , ik−1 . In equation 48, the two braces associated with v1 and v2 share the term r(s, a), so for every a ∈ A their difference is N
γ X v1 v2 Uk+1,c − Uk+1,c θk (s, a), i0 , . . . , ik , N i =1 k
whose absolute value is at most γ ℓ−k ∥v1 −v2 ∥∞ by the induction hypothesis. Since maximizing over v1 v2 a is 1-Lipschitz, the same bound holds for |Uk,c (s, i0 , . . . , ik−1 ) − Uk,c (s, i0 , . . . , ik−1 )|, uniformly in c. The case k = 0 is equation 53. For equation 54, the term r(s, a) cancels likewise in equation 49, e v (s, c, a) − Q e v (s, c, a)| equals γ times an average of differences at level 1, hence is at most so |Q 1 2 ℓ−1 γ · γ ∥v1 − v2 ∥∞ . Remark 2 (Deployment cost). Proceeding level by level as in equation 44, the cost of computing all action scores for one queried pair (s, c) is ! ℓ−1 X k+1 k O nN + nmN = O ℓn(m + 1)N ℓ . (55) k=0
Moreover, note that the terminal array v, of size nN ℓ , is already stored. During an online query, v v the largest temporary array is Uℓ−1,c , which contains nN ℓ−1 entries. Indeed, once Uk,c has been v v computed from Uk+1,c , the array Uk+1,c is no longer needed and can be discarded. Thus, the online computation requires only O(nN ℓ−1 ) additional working memory. Run Algorithm 1 with
8 N= 2 ε (1 − γ)4 and
K=
2 log + 1 + (ℓ − 1)nm log n δ
1 4 log . 1−γ ε(1 − γ)
It returns D = (Θ1 , . . . , ΘN , v K ), and Algorithm 2 defines the policy πD . Apply Lemma 3 with ε(1 − γ)2 Vmax . 4 The above choice of N ensures that the failure probability in equation 37 is at most δ. Therefore, with probability at least 1 − δ, Lemma 5 gives b ⋆ (s, c, a) − Q⋆ (s, c, a) ≤ γη sup Q ℓ 1−γ s,c,a ε(1 − γ)Vmax ≤ . (56) 4 η=
By the choice of K, ∥v K − v ⋆ ∥∞ ≤ γ K Vmax ≤ e−(1−γ)K Vmax ε(1 − γ)Vmax ≤ . 4 Lemma 8 then implies e vK (s, c, a) − Q b ⋆ (s, c, a) ≤ γ ℓ ∥v K − v ⋆ ∥∞ sup Q
s,c,a
≤
21
ε(1 − γ)Vmax . 4
(57)
Combining equation 56 and equation 57 yields e vK (s, c, a) − Q⋆ℓ (s, c, a) ≤ ε(1 − γ)Vmax . sup Q 2 s,c,a
(58)
e vK (s, c, ·). It follows Fix (s, c), let a⋆ maximize Q⋆ℓ (s, c, ·), and recall that πD (s, c) maximizes Q from equation 58 that Vℓ⋆ (s, c) = Q⋆ℓ (s, c, a⋆ ) ε(1 − γ)Vmax 2 ε(1 − γ)Vmax e vK (s, c, πD (s, c)) + ≤Q 2 ≤ Q⋆ℓ (s, c, πD (s, c)) + ε(1 − γ)Vmax . e vK (s, c, a⋆ ) + ≤Q
Let TℓπD denote the Bellman operator of πD in the true augmented MDP. The preceding inequality is equivalent to Vℓ⋆ ≤ TℓπD Vℓ⋆ + ε(1 − γ)Vmax 1. Since VℓπD = TℓπD VℓπD and TℓπD is a γ-contraction, ∥Vℓ⋆ − VℓπD ∥∞ ≤ γ∥Vℓ⋆ − VℓπD ∥∞ + ε(1 − γ)Vmax . Rearranging gives
∥Vℓ⋆ − VℓπD ∥∞ ≤ εVmax ,
which proves equation 7 simultaneously for every (s, c) ∈ S × Ωℓ . It remains to verify the computational guarantees. Sampling the N dictionary tables costs O(N nm), and the K value-iteration steps cost O Kn(m + 1)N ℓ . Hence the total preprocessing time is O N nm + Kn(m + 1)N ℓ . The policy representation D = (Θ1 , . . . , ΘN , v K ) occupies O N nm + nN ℓ memory locations. e vK (s, c, a) costs For a given state s and observed window c, computing all the scores Q O ℓn(m + 1)N ℓ . The observed window occupies O(ℓnm) memory locations. Moreover, the arrays used during this computation can be discarded level by level, so the temporary memory does not exceed O(nN ℓ−1 ). The total memory used during online action selection is therefore O N nm + nN ℓ + ℓnm . Finally, N =O
! log(1/δ) + 1 + (ℓ − 1)nm log n , ε2 (1 − γ)4
K=O
log(1/[ε(1 − γ)]) 1−γ
.
Thus, for every fixed ℓ, preprocessing time, representation size, and per-decision computation are polynomial in n, m, ε−1 , log(1/δ), and (1 − γ)−1 . This completes the proof.
22
A.3
P ROOF OF THEOREM 3
We prove the regret bound for DLA-UCB. After N transition tables have expired, the learner has observed N independent samples from every row P (· | s, a). It therefore uses the usual empirical transition kernel and reconstructs the corresponding product law: N −1 1 X ′ b PN (s | s, a) := 1{Θj (s, a) = s′ }, N j=0 O b N := Q PbN (· | s, a).
(59)
(s,a)∈S×A
The following lemma shows that, for every fixed value function, the product estimator satisfies the same Bernstein inequality as an average of N independent complete transition tables. Lemma 9 (Product-estimator Bernstein bound). Let Θ0 , . . . , ΘN −1 be independent transition tables b N be defined by equation 59. Then, for every fixed function V : Ω → with distribution Q, and let Q [0, Vmax ] and every x > 0, ! r 2 VarQ (V )x Vmax x + ≤ 2e−x . (60) P EQ b N [V ] − EQ [V ] > N 3N Proof. For every (s, a) ∈ S ×A, let πs,a be an independent uniform permutation of {0, . . . , N −1}, independent of the observed tables. For each j, define Θπj (s, a) := Θπs,a (j) (s, a),
V
π
N −1
:=
1 X V (Θπj ). N j=0
Conditionally on the observations, the permutations select every coordinate independently and uniformly from its empirical marginal. Therefore, i h π Eπ V Θ0 , . . . , ΘN −1 = EQ (61) b N [V ]. For every fixed collection of permutations, the rematched tables Θπ0 , . . . , ΘπN −1 are independent and identically distributed according to Q. Indeed, at each coordinate the permutation uses distinct observations, while all observations belonging to different coordinates are independent under the product model. For every λ ∈ R, Jensen’s inequality and equation 61 give E exp λ[EQ [V ] − E [V ]] Q bN π ≤ EEπ exp λ[V − EQ [V ]] . For fixed permutations, the right-hand side is the moment generating function of the average of N independent copies of V (Θ) − EQ [V ]. The scalar Bernstein bound therefore applies with variance VarQ (V ). Applying its upper-tail form to V , its lower-tail form to −V , and taking a union bound proves equation 60. We now apply Lemma 9 to the continuation values generated by Vℓ⋆ . Define ! 2n|Ω|ℓ−1 1 + ⌈log2 T ⌉ ιT (δ) := log . δ
(62)
Lemma 10 (Uniform confidence for optimal continuation values). With probability at least 1 − δ, simultaneously for every transition sample size N used by the planner up to time T , every u ∈ S, and every θ1:ℓ−1 ∈ Ωℓ−1 ,, and every θ1:ℓ−1 ∈ Ωℓ−1 , ⋆ ⋆ EΘ∼Q b N [Vℓ (u, θ1:ℓ−1 , Θ)] − EΘ∼Q [Vℓ (u, θ1:ℓ−1 , Θ)] r 2 VarΘ∼Q (Vℓ⋆ (u, θ1:ℓ−1 , Θ)) ιT (δ) Vmax ιT (δ) ≤ + . N 3N
23
(63)
Proof. Fix N , u, and θ1:ℓ−1 , and consider the function Vℓ⋆ (u, θ1:ℓ−1 , θ), θ ∈ Ω. This function takes values in [0, Vmax ] and is fixed independently of the transition observations. Lemma 9, applied with x = ιT (δ), therefore gives equation 63 with failure probability at most 2e−ιT (δ) . The planner uses at most 1 + ⌈log2 T ⌉ distinct transition sample sizes up to time T . A union bound thus gives a total failure probability of at most 2n|Ω|ℓ−1 1 + ⌈log2 T ⌉ e−ιT (δ) = δ.
Since |Ω| = nnm , log n|Ω|ℓ−1 = 1 + (ℓ − 1)nm log n. Thus, although the number of possible look-ahead suffixes is exponential, its contribution to the confidence radius is only logarithmic. Lemma 10 cannot be applied directly to the optimistic value function, since that function is conb N . We therefore complement it with a weaker structed from the same transition observations as Q bound that holds simultaneously for every bounded function. For every dyadic N ≤ T , define v u u n2 m log(N + 1) + log 1+⌈log2 T ⌉ t δ . ρN (δ) := min 1, 2N
(64)
Lemma 11 (Uniform control of the value function). With probability at least 1 − δ, simultaneously for every transition sample size N used by the planner up to time T , and every function V : Ω → [0, Vmax ], EΘ∼Q b N [V (Θ)] − EΘ∼Q [V (Θ)] p √ ≤ 2 2 ρN (δ) VarΘ∼Q (V (Θ)) + 2Vmax ρ2N (δ),
(65)
q p VarΘ∼Q VarΘ∼Q (V (Θ)) ≤ 2Vmax ρN (δ). b N (V (Θ)) −
(66)
and
In particular, these inequalities remain valid when V is selected after observing Θ0 , . . . , ΘN −1 . P p Proof. For distributions p, q on Ω, let H 2 (p, q) = 1 − θ p(θ)q(θ). Writing µ = Eq [V ] and √ √ √ √ √ p − q = ( p − q) 2 q + p − q , √ √ Cauchy–Schwarz and ∥ p − q∥22 = 2H 2 (p, q) give q √ |Ep [V ] − Eq [V ]| ≤ 2 2 H(p, q) Varq (V ) + 2Vmax H 2 (p, q). Moreover,
q √ Varp (V ) = inf ∥(V − c) p∥2 . c∈R
Evaluating the infimum at c = Eq [V ], applying the triangle inequality, and then exchanging p and q yields q q Varp (V ) − Varq (V ) ≤ 2Vmax H(p, q). Finally, the method of types, KL tensorization, and 2H 2 ≤ KL imply δ b N , Q) > ρN (δ) ≤ P H(Q . 1 + ⌈log2 T ⌉ A union bound over the planner update sample sizes completes the proof. 24
Unlike Lemma 10, this result is uniform over V . We will use its larger radius only to control the datadependent difference between the optimistic value function and Vℓ⋆ . We now combine the Bernstein and Hellinger bounds into the optimistic expectation used by the planner. For every dyadic N ≤ T , let ( r ) ιT (δ) αN := min 1, , ρN := ρN (δ), (67) N and, for V : Ω → [0, Vmax ], write σ bN (V ) :=
q
VarΘ∼Q b N (V (Θ)).
Define n UCBN (V ) := min Vmax , EΘ∼Q b N [V (Θ)] + 8Vmax αN ρN o 2 . + max 7αN σ bN (V ), 49Vmax αN
(68)
The second term inside the maximum ensures that the optimistic expectation remains monotone in the value function. Lemma 12 (Properties of the optimistic expectation). On the intersection of the events in Lemmas 10 and 11, the following properties hold simultaneously for every dyadic N ≤ T . 1. The mapping V 7−→ UCBN (V ) is nondecreasing for the pointwise order and is 1-Lipschitz in the supremum norm. 2. For every u ∈ S and θ1:ℓ−1 ∈ Ωℓ−1 , the optimal continuation value V (θ) := Vℓ⋆ (u, θ1:ℓ−1 , θ) satisfies UCBN (V ) ≥ EΘ∼Q [V (Θ)].
(69)
3. Let W : Ω → [0, Vmax ] be any possibly data-dependent function such that W ≥ V pointwise. There exists a constant C s.t. " p UCBN (W ) − EΘ∼Q [W (Θ)] ≤ C αN VarΘ∼Q (V (Θ)) p + (αN + ρN ) Vmax EΘ∼Q [W (Θ) − V (Θ)] # + Vmax (αN + ρN )2
(70)
Proof. (1.) Consider the expression inside the outer minimum in equation 68. Fix θ ∈ Ω, hold all 2 other values of V fixed, and increase V (θ) . If the maximum in equation 68 equals 49Vmax αN , its derivative with respect to V (θ) is simply b N (θ) ≥ 0. Q If the maximum equals 7αN σ bN (V ), then necessarily 2 7αN σ bN (V ) ≥ 49Vmax αN ,
and therefore σ bN (V ) ≥ 7Vmax αN . Whenever σ bN (V ) > 0, the derivative of the empirical mean plus the variance bonus is ! V (θ) − EQ b N [V ] b QN (θ) 1 + 7αN . σ bN (V ) 25
Since V (θ) − EQ b N [V ] ≥ −Vmax ,
(71)
this derivative is at least
7αN Vmax b QN (θ) 1 − ≥ 0. (72) σ bN (V ) When the two terms inside the maximum are equal, the expression remains continuous, so increasing V (θ) cannot produce a downward jump. If σ bN (V ) = 0, the constant term is selected unless αN = 0, in which case the expression reduces to the empirical mean. Thus, increasing any value V (θ) cannot decrease UCBN (V ). Consequently, if V (θ) ≤ W (θ) for every θ ∈ Ω, then UCBN (V ) ≤ UCBN (W ).
(73)
The additive term 8Vmax αN ρN and the clipping at Vmax clearly preserve this property. It remains to prove the Lipschitz property. The preceding argument uses only that the difference between any value of the function and its mean is at least −Vmax ; it therefore remains valid after adding a constant to the function. Since V ≤ W + ∥V − W ∥∞
(74)
pointwise, monotonicity and the fact that adding a constant changes the empirical mean by that constant but leaves the empirical standard deviation unchanged give UCBN (V ) ≤ UCBN (W ) + ∥V − W ∥∞ .
(75)
Exchanging V and W yields |UCBN (V ) − UCBN (W )| ≤ ∥V − W ∥∞ .
(76)
This proves the first property. (2.) First, note that max{7x, 49y} ≥ 2x + 5y,
x, y ≥ 0,
(77)
If αN = 1, then UCBN (V ) = Vmax , so equation 69 is immediate. Suppose therefore that αN < 1. Lemma 10 gives EQ [V ] − EQ b N [V ] ≤
√
2αN
2 p Vmax αN VarQ (V ) + . 3
By Lemma 11, p
VarQ (V ) ≤ σ bN (V ) + 2Vmax ρN .
Consequently, 2 √ Vmax αN 2αN σ bN (V ) + 2 2Vmax αN ρN + . 3 The bonus in equation 68 dominates the right-hand side by equation 77, proving equation 69.
EQ [V ] − EQ b N [V ] ≤
√
(3.) If αN = 1, the result follows immediately after enlarging C, since both expectations lie in [0, Vmax ]. Assume henceforth that αN < 1 and write D := W − V ≥ 0. Since clipping can only decrease the optimistic estimate, UCBN (W ) − EQ [W ] ≤ EQ b N [V ] − EQ [V ]
+ EQ b N [D] − EQ [D] + 8Vmax αN ρN 2 + 7αN σ bN (W ) + 49Vmax αN .
(78)
The first difference is controlled by Lemma 10. Since D may depend on the observations, we use instead Lemma 11: p √ Vmax EQ [D] + 2Vmax ρ2N , (79) EQ b N [D] − EQ [D] ≤ 2 2ρN 26
where we used
VarQ (D) ≤ EQ [D2 ] ≤ Vmax EQ [D].
Finally, the triangle inequality for standard deviations and Lemma 11 give σ bN (W ) ≤ σ bN (V ) + σ bN (D) p p ≤ VarQ (V ) + VarQ (D) + 4Vmax ρN p p ≤ VarQ (V ) + Vmax EQ [D] + 4Vmax ρN . Substituting these bounds into equation 78 and collecting terms proves equation 70. We now insert the optimistic expectation into the Bellman operator. Consider a planner update using N past transition tables and an optimistic reward function r+ : S × A → [0, Rmax ]. For every bounded value function V and every window c = (θ0 , . . . , θℓ−1 ), define n o (T N,r+ V )(s, c) := max min Vmax , r+ (s, a) + γ UCBN θ 7→ V (θ0 (s, a), θ1 , . . . , θℓ−1 , θ) . a∈A
(80) Let V N,r+ denote its fixed point. The corresponding action scores are n o QN,r+ (s, c, a) := min Vmax , r+ (s, a) + γ UCBN θ 7→ V N,r+ (θ0 (s, a), θ1 , . . . , θℓ−1 , θ) . (81) Lemma 13 (Contraction and optimism of the ideal planner). On the events of Lemmas 10 and 11, if r+ ≥ r pointwise, then T N,r+ is a monotone γ-contraction and V N,r+ (s, c) ≥ Vℓ⋆ (s, c)
for every (s, c) ∈ S × Ωℓ .
(82)
Proof. Lemma 12 shows that UCBN is monotone and 1-Lipschitz. Maximization over actions and clipping preserve these properties. Therefore, for any two bounded value functions V and V ′ , T N,r+ V − T N,r+ V ′ ∞ ≤ γ∥V − V ′ ∥∞ . Hence, T N,r+ has a unique fixed point. Fix a window c = (θ0 , . . . , θℓ−1), a state s, and an action a. Applying equation 69 to the function θ 7→ Vℓ⋆ θ0 (s, a), θ1 , . . . , θℓ−1 , θ and using r+ ≥ r gives T N,r+ Vℓ⋆ ≥ Tℓ Vℓ⋆ = Vℓ⋆ . By monotonicity, T N,r+
k
Vℓ⋆ ≥ Vℓ⋆
for every k ≥ 1.
The contraction property implies that the left-hand side converges to V N,r+ . Letting k → +∞ proves equation 82. The operator in equation 80 is used only in the analysis. To approximate its expectations efficiently, conditionally on the tables observed before the current planner update, the planner draws N 1 MN i.i.d. b Z ,...,Z ∼ QN , MN = . (83) (1 − γ)3 For later use, denote the empirical distribution of the dictionary by QD N :=
MN 1 X δ j, MN j=1 Z
D σN (V ) :=
q
VarΘ∼QD (V (Θ)). N
Let v : S × [MN ]ℓ → [0, Vmax ] be the current value array. For a dictionary state (s, i0 , . . . , iℓ−1 ) and an action a, define the empirical continuation mean by v(s, a, i0 , . . . , iℓ−1 ) :=
MN 1 X v Z i0 (s, a), i1 , . . . , iℓ−1 , j , MN j=1
27
and its empirical variance by s2v (s, a, i0 , . . . , iℓ−1 ) :=
MN 2 1 X v Z i0 (s, a), i1 , . . . , iℓ−1 , j − v(s, a, i0 , . . . , iℓ−1 ) . MN j=1
The optimistic continuation estimate associated with v is UCBD N (v; s, a, i0 , . . . , iℓ−1 ) ( := min Vmax , v(s, a, i0 , . . . , iℓ−1 ) + 8Vmax αN ρN ) o n 2 + max 7αN sv (s, a, i0 , . . . , iℓ−1 ), 49Vmax αN . The corresponding Bellman operator is D,+ (TN,r + v)(s, i0 , . . . , iℓ−1 ) := max min Vmax , r+ (s, a) + γ UCBD N (v; s, a, i0 , . . . , iℓ−1 ) .
(84)
a∈A
Value iteration applies equation 84 to the dictionary states. For a window c ∈ Ωℓ observed during interaction, the backward extension applies the same update successively to the tables in c. Thus, the b N by their empirical counterfinite planner replaces the expectation and standard deviation under Q parts over the sampled dictionary. For a window c = (θ0 , . . . , θℓ−1 ) observed during interaction, the backward extension of Algorithm 3 uses the same empirical continuation estimate at every level. We e N,r+ (s, c, a) the resulting action score when action a is kept fixed at the first Bellman denote by Q update. Lemma 14 (Concentration of a sample mean and standard deviation). Let Y1 , . . . , YM ∈ [0, B] be i.i.d. random variables, and let µ bM and σ bM be their empirical mean and empirical standard deviation, with denominator M . For every x ≥ 1, with probability at least 1 − 6e−x , r r p 2x x |b µM − E(Y )| ≤ B , |b σM − Var(Y )| ≤ 5B . (85) M M Proof. The mean bound follows from Hoeffding’s inequality, and the standard-deviation bound follows from Theorem 10 of Maurer & Pontil (2009), after rescaling to [0, B] and accounting for the use of denominator M . A union bound completes the proof. Let ET be the total number of planner updates up to time T . Under the update rule of DLA-UCB, ET ≤ 2 + (1 + nm) 1 + ⌈log2 T ⌉ . (86) Indeed, the global number of expired tables and each of the nm reward counts can double at most 1 + ⌈log2 T ⌉ times. Define 12ET n|Ω|ℓ−1 D LT (δ) := log . (87) δ e t (s, c, a) denotes the action score computed by the backward extension of the planning Recall that Q object used at time t. If its most recent update used N transition tables and reward bound r+ , we compare this computed score with the ideal score QN,r+ (s, c, a) defined in equation 81. Lemma 15 (Accuracy of the dictionary planner). Suppose that, at each planner update, the dictiol m 2 N 1 nary is sampled as in equation 83, with MN ≥ (1−γ)3 . If value iteration is run for 1−γ log 2N 1−γ iterations, then, with probability at least 1 − δ, at every planner update, s LD Rmax T (δ) e sup QN,r+ (s, c, a) − QN,r+ (s, c, a) ≤ CRmax + . (88) N (1 − γ) N2 s∈S, c∈Ωℓ , a∈A 28
b N and r+ have already been computed from the Proof. Consider one planner update. At this point, Q previously observed transition tables and rewards. We treat these quantities as fixed and consider only the randomness of the new dictionary Z 1 , . . . , Z MN , which is sampled independently from b N . Then Q b N , r+ , and the exact-expectation fixed point V N,r+ are fixed, whereas Z 1 , . . . , Z MN Q b N . For every u ∈ S and θ1:ℓ−1 ∈ Ωℓ−1 , apply Lemma 14 to are independent samples from Q Z 7−→ V N,r+ (u, θ1:ℓ−1 , Z). A union bound over the states, suffixes, and planner updates gives, simultaneously, s LD T (δ) + ] − E b [V N,r + ] ≤ CVmax EQD [V , N,r Q N N MN and s LD D T (δ) bN (V N,r+ ) ≤ CVmax σN . (V N,r+ ) − σ MN The state and suffixarguments are omitted. The optimistic continuation estimate is the sum of 2 the mean and max 7αN σ, 49Vmax αN . Since αN ≤ 1, changing the mean and standard deviation q by at most the preceding amount changes the optimistic continuation estimate by at most LD T (δ) CVmax MN . Maximization over actions and clipping cannot increase this error. Therefore, s LD D T (δ) T N,r+ V N,r+ − T N,r+ V N,r+ ≤ CγVmax . MN ∞ D
D
Denote the fixed point of T N,r+ by V N,r+ . Since both operators are γ-contractions, D
V N,r+ − V N,r+
D
∞
D
D
≤ T N,r+ V N,r+ − T N,r+ V N,r+ +
∞ D T N,r+ V N,r+ − T N,r+ V N,r+ D
≤ γ V N,r+ − V N,r+
∞
+ CγVmax
∞ s
LD T (δ) . MN
Rearranging gives s CγVmax LD T (δ) . ≤ 1−γ MN ∞ The restriction, extension, and stability arguments of Lemmas 6, 7, and 8 apply unchanged to the dictionary operator, since the same optimistic continuation estimate is used in the finite value iteration and in the backward extension. Hence the backward extension introduces no additional approximation, while stopping value iteration after KN iterations contributes at most γ KN Vmax . The difference between the scores returned after convergence and QN,r+ (s, c, a) is therefore at most s CVmax LD T (δ) . 1−γ MN D V N,r+ − V N,r+
This proves equation 88. Conditional on the expired tables, concentration is applied only to the ideal fixed point, which is independent of the fresh dictionary; contraction then transfers the estimate to the dictionary-dependent fixed point. For a state–action pair visited k ≥ 1 times, let rbk (s, a) be the empirical reward mean. At each planner update triggered by a doubled reward count, define ( ) r R (δ) 2L T UkR (s, a) := min Rmax , rbk (s, a) + Rmax , k 8nm(1 + ⌈log2 T ⌉) . (89) δ For an unvisited pair, set U0R (s, a) = Rmax . As in the main algorithm, r+ is the minimum of all successive upper bounds for that pair. LR T (δ) := log
29
Lemma 16 (Reward confidence). With probability at least 1 − δ, r(s, a) ≤ rt+ (s, a) and
T −1 X
for every t, s, a,
(90)
q R nmT LR (δ) + nmL (δ) . rt+ (St , At ) − r(St , At ) ≤ CRmax T T
(91)
t=0
Proof. Hoeffding’s inequality and a union bound over the nm pairs and their dyadic counts prove equation 90. On this event, if the current visit count of a pair is j, the estimate used by the algorithm was computed from at least j/2 observations. Its width is therefore at most s LR T (δ) CRmax . j∨1 p PNT (s,a) −1/2 For a pair visited NT (s, a) times, j=1 j ≤ 2 NT (s, a). Summing over pairs and applying Cauchy–Schwarz gives Xp √ NT (s, a) ≤ nmT . s,a
The first visits and the linear parts of the confidence radii contribute the second term in equation 91.
At time t ≥ 1, let Nt denote the number of transition tables used by the current planner. Since the planner is updated whenever this number doubles, 2t ≤ Nt ≤ t. For every transition sample size N used by the planner, define s LD Rmax T (δ) + . (92) εD N := CRmax N (1 − γ) N2 Lemma 17 (Cumulative confidence bounds). For fixed ℓ, T −1 X
2 e αN = O(nm), t
(93)
t=1 T −1 X
αNt + ρNt
2
e 2 m), = O(n
(94)
t=1 T −1 X
s e εD Nt = O
Rmax
t=1
nmT 1−γ
! .
Where αNt is defined 67, ρNt is defined 64, εNt is defined Proof. The definitions of the confidence radii give 2 nm n m 2 2 e e , ρN ≤ 1 ∧ O . αN ≤ 1 ∧ O N N Consequently, αN + ρN
2
e ≤4∧O
n2 m N
.
Since Nt ≥ t/2, T −1 X
1 = O(log T ), Nt t=1
T −1 X
√ 1 √ = O( T ), Nt t=1
T −1 X
1 = O(1). Nt2 t=1
Summing the preceding bounds proves equation 93 and equation 94. 30
(95)
Moreover, equation 92 gives r e εD = O R max N
nm Rmax + N (1 − γ) N2
.
Summing this inequality and using the last two bounds above proves equation 95. Let e(t) denote the planner epoch active at time t, and abbreviate Dt := Wt − Vℓ⋆ .
Wt := WNt ,r+ , t
The function Dt is fixed within each planner epoch and, by Lemma 13, 0 ≤ Dt (x) ≤ Vmax ,
x ∈ X.
(96)
Let Ft contain the history and the current look-ahead window before At is chosen. Define µt := E [Dt (Xt+1 ) | Ft ] ,
(97)
σt2 := Var (Vℓ⋆ (Xt+1 ) | Ft ) .
(98)
Conditionally on Ft , the only randomness in Xt+1 is the fresh table Θt+ℓ . Hence these are precisely the mean and variance under Q appearing in Lemma 12. Lemma 18 (One-step optimistic recursion). On the joint transition, reward, and dictionary confidence event, the action selected by DLA-UCB satisfies Dt (Xt ) + Vℓ⋆ (Xt ) − Q⋆ℓ (Xt , At ) ≤ rt+ (St , At ) − r(St , At ) + 2εD Nt + γµt i h p + Cγ αt σt + βt Vmax µt + Vmax βt2 .
(99)
Proof. By equation 88, the action maximizing the computed dictionary score is 2εD Nt -greedy for the ideal scores: Wt (Xt ) ≤ QNt ,r+ (Xt , At ) + 2εD Nt . t
Consequently, Dt (Xt ) + Vℓ⋆ (Xt ) − Q⋆ℓ (Xt , At ) = Wt (Xt ) − Q⋆ℓ (Xt , At ) ≤ rt+ (St , At ) − r(St , At ) + 2εD Nt + γ UCBNt ((Wt )Xt ,At ) − E Vℓ⋆ (Xt+1 ) | Ft . Clipping cannot invalidate this upper bound because Q⋆ℓ ≤ Vmax . Add and subtract E[Wt (Xt+1 ) | Ft ]. The added difference is µt , and equation 70, with V = (Vℓ⋆ )Xt ,At and W = (Wt )Xt ,At , bounds the remaining term. This proves equation 99. The first lemma converts predictable nonnegative quantities into their realized counterparts without √ paying a T term. Lemma 19 (Predictable-to-realized comparison). Let Yt ∈ [0, B] be Ft+1 -measurable and let µt = E[Yt | Ft ]. For every η ∈ (0, 1], with probability at least 1 − δ, T −1 X
T −1 X
µt ≤ (1 + η)
t=0
Yt
t=0
2B log(1/δ) . η
(100)
Proof. For λ ∈ (0, 1], conditional Jensen’s inequality for exp(−λYt /B) gives h i µt E e−λYt /B | Ft ≤ exp −(1 − e−λ ) . B The corresponding product is a nonnegative supermartingale. Ville’s inequality therefore gives, with probability at least 1 − δ, X X (1 − e−λ ) µt ≤ λ Yt + B log(1/δ). t
For λ ∈ (0, 1], λ/(1 − e
−λ
t −λ −1
) ≤ 1 + λ and (1 − e
)
31
≤ 2/λ. Taking λ = η proves the result.
The next result is the discounted law of total variance needed for the Bernstein term. Lemma 20 (Discounted total variance). Let GT :=
T −1 X
[Vℓ⋆ (Xt ) − Q⋆ℓ (Xt , At )] .
t=0
With probability at least 1 − δ, T −1 X
γ 2 σt2 ≤ C
t=0
1 2 . Vmax Rmax T + Vmax GT + Vmax log δ
(101)
Proof. Write vt := Vℓ⋆ (Xt ),
gt := Vℓ⋆ (Xt ) − Q⋆ℓ (Xt , At ),
yt := r(St , At ) + gt .
The Bellman equation gives vt = yt + γE[vt+1 | Ft ]. All terms are nonnegative, and 0 ≤ yt ≤ vt ≤ Vmax . Using equation 102,
(102)
2 γ 2 σt2 = γ 2 E[vt+1 | Ft ] − (vt − yt )2 2 ≤ γ 2 E[vt+1 | Ft ] − vt2 + 2Vmax yt . 2 Summing and inserting the realized vt+1 yields T −1 X
2 γ 2 σt2 ≤ Vmax + 2Vmax (Rmax T + GT ) + MT ,
(103)
t=0
where MT :=
T −1 X
2 2 γ 2 E[vt+1 | Ft ] − vt+1
t=0
is a martingale. If ST :=
2 2 t γ σt , then X 2 2 Var γ 2 vt+1 | Ft ≤ 4Vmax ST .
P
t 2 σt2 . Indeed, z 7→ z 2 is 2Vmax -Lipschitz on [0, Vmax ], so its conditional variance is at most 4Vmax Freedman’s inequality therefore gives
MT ≤
p
2 S log(1/δ) + 8Vmax T
Substitute this into equation 103 and use This proves equation 101.
√
2 Vmax 1 log . 3 δ
ab ≤ a/2 + b/2 to absorb ST /2 into the left-hand side.
Lemma 21 (Summing the optimistic recursion). On an event of probability at least 1 − δ, " T −1 −1 X TX GT ≤ C rt+ (St , At ) − r(St , At ) + εD Nt t=0 T −1 X
t=1 T −1 X
Vmax βt2 1 − γ t=1 t=1 # Vmax log(1/δ) + Vmax ET + . 1−γ +
γαt σt +
(104)
Proof. The first decision contributes at most Vmax , which can be absorbed into the last two terms. Sum equation 99 from t = 1 to T − 1. Set µt = E[Yt | Ft ].
Yt := Dt (Xt+1 ), 32
Within a planner epoch {p, . . . , q}, Dt is a fixed function, and hence q X
[γDt (Xt+1 ) − Dt (Xt )] = −Dt (Xp ) + Dt (Xq+1 ) − (1 − γ)
t=p
q X
Yt
t=p
≤ Vmax − (1 − γ)
q X
Yt .
t=p
Summing over epochs and replacing Yt by µt , the potential terms are therefore bounded by X X Vmax ET + γ µt − Yt . t
(105)
t
Use Young’s inequality in the adaptive square-root term: Cγβt
p
Vmax µt ≤
1 − γ CVmax βt2 µt . 8 1−γ
Let γ̄ := γ + (1 − γ)/8 and apply Lemma 19 with η = (1 − γ)/4. Since γ̄(1 + η) ≤ 1 − we obtain γ̄
X
µt −
t
X t
Yt ≤ −
1−γ , 2
1 − γ X CVmax log(1/δ) Yt . 2 1−γ t
Discarding the negative term and collecting the remaining contributions proves equation 104. Completion of the proof of Theorem 3. Invoke all preceding confidence events with failure probabilities that sum to at most δ. By Cauchy–Schwarz, v u T −1 T −1 u X X γαt σt ≤ tAT (106) γ 2 σt2 . t=1
t=1
Lemmas 17 and 20 imply T −1 X
s γαt σt ≤ C
t=1
1 2 AT Vmax Rmax T + Vmax GT + Vmax log . δ
(107)
The term involving GT is absorbed through p 1 C AT Vmax GT ≤ GT + C ′ AT Vmax . 4 We now substitute the reward bound equation 91, the coefficient and dictionary bounds equation 93– equation 95, and the epoch bound equation 86 into equation 104. Together with equation 107 and Vmax = Rmax /(1 − γ), this gives s ! 2 m nmT R n max e Rmax Regℓ (T ) = GT ≤ O + . (108) 1−γ (1 − γ)2 For fixed ℓ, all suppressed factors are logarithmic in n, m, T, δ −1 , and (1 − γ)−1 . This proves the claimed high-probability regret bound.
B
E XPERIMENTS
We evaluate our planner on the wind-farm storage-control benchmark of Lu et al. (2025), reusing their CAISO wind-generation forecasts and observations, their electricity-price series, their preprocessed arrays, their state and action discretisation, and their evaluation interval. 33
C
E XTENSION TO NOISY TRANSITION LOOK - AHEAD
This section extends DLA-UCB to locally corrupted transition look-ahead. We first specify the observation model and the correct comparator, and then give the complete algorithm and regret analysis. The reward-confidence construction is unchanged from Appendix A.3. C.1
N OISY TRANSITION LOOK - AHEAD
Recall that Ω = S S×A and that the transition tables are i.i.d. with product law Y Q(θ) = P θ(s, a) | s, a .
(109)
(s,a)∈S×A
For every (s, a, s′ ), let I(· | s, a, s′ ) be a distribution on S. Conditional on Θt = θ, the noisy table e t is sampled according to Θ Y e a) | s, a, θ(s, a) . e t = θe | Θt = θ = I θ(s, P Θ (110) (s,a)∈S×A
e t ) are independent across time. Before choosing At , the learner observes The pairs (Θt , Θ etℓ := (Θ e t, . . . , Θ e t+ℓ−1 ), C
(111)
whereas the true transition remains St+1 = Θt (St , At ). After acting, the learner observes only (Rt , St+1 ); in particular, it never observes the complete table Θt . e be the marginal law of a noisy table. It is again a product distribution. The true successor Let Q conditional on the noisy entry is governed by e t (s, a) = z . Pe(s′ | s, a, z) := P Θt (s, a) = s′ | Θ (112) Whenever the conditioning event has positive probability, Bayes’ rule gives ′
′
P (s | s, a)I(z | s, a, s ) Pe(s′ | s, a, z) = P . u∈S P (u | s, a)I(z | s, a, u)
(113)
The value of the posterior can be chosen arbitrarily on null conditioning events. The product assumptions imply the following identity e a) . e t = θe = Pe s′ | s, a, θ(s, P Θt (s, a) = s′ | Θ (114) For V : S × Ωℓ → [0, Vmax ], the Bellman operator is consequently (Teℓ V )(s, θe0:ℓ−1 ) ( := max r(s, a) + γ a∈A
X
) h i ′ ′ e e e e P s | s, a, θ0 (s, a) EΘ∼ . e V (s , θ1:ℓ−1 , Θ) e Q
(115)
s′ ∈S
It is a monotone γ-contraction. Its fixed point and associated action scores are denoted by Veℓ⋆ and e ⋆ . The oracle observes the same noisy windows as the learner; it does not observe the latent tables. Q ℓ We measure regret by g ℓ (T ) := Reg
T −1 h X
i etℓ ) − Q e ⋆ℓ (St , C etℓ , At ) . Veℓ⋆ (St , C
(116)
t=0
C.2
N EAR - OPTIMAL PLANNING
e and evaluate Pe. Draw once and for all Suppose first that one can sample from Q e e 1, . . . , Θ e N i.i.d. Θ ∼ Q. 34
(117)
On CN = S × [N ]ℓ , define (TeN v)(s, i0 , . . . , iℓ−1 ) ( := max r(s, a) + γ a∈A
X s′ ∈S
) N 1 X ′ i0 ′ e e P s | s, a, Θ (s, a) v(s , i1 , . . . , iℓ−1 , j) . N j=1
(118)
Starting from Ve 0 = 0, run Ve k+1 = TeN Ve k . For an arbitrary observed window e c = (θe0 , . . . , θeℓ−1 ), set e V (s, i0 , . . . , iℓ−1 ) := V (s, i0 , . . . , iℓ−1 ), U ℓ,e c
and, for k = ℓ − 1, . . . , 0, define e V (s, i0 , . . . , ik−1 ) U k,e c ( ) N X 1 X ′ V ′ e := max r(s, a) + γ Pe s | s, a, θek (s, a) (s , i0 , . . . , ik ) . U a∈A N i =1 k+1,ec ′ s ∈S
(119)
(120)
k
e v (s, e At k = 0 the index list is empty. Keeping the root action fixed defines Q c, a), and the returned e policy is greedy with respect to QveK . Theorem 4 (RPTAS for noisy transition look-ahead). Fix ℓ ≥ 2 and ε, δ ∈ (0, 1). For suitable choices of the sample size N and the number of value-iteration steps K, the algorithm described above computes a policy π eD such that π e D P Veℓ (s, e c) ≥ Veℓ⋆ (s, e c) − εVmax , ∀(s, e c) ∈ S × Ωℓ ≥ 1 − δ. (121) For every fixed ℓ, computing and storing the policy, as well as selecting an action at each decision time, require time and memory polynomial in n, m, ε−1 , log(1/δ), and (1 − γ)−1 . b e N = N −1 PN δ e j . For each s′ and noisy suffix, apply Hoeffding’s inequality to Proof. Let Q j=1 Θ e 7→ Ve ⋆ (s′ , θe1:ℓ−1 , Θ) e and take a union bound over the n|Ω|ℓ−1 = n1+(ℓ−1)nm possible functions. Θ ℓ Set η = ε(1 − γ)2 Vmax /16. A sufficient choice is 2 128 log [1 + (ℓ − 1)nm] log n . (122) N≥ 2 ε (1 − γ)4 δ Then, with probability at least 1 − δ, all the corresponding empirical and true expectations differ by at most η. Averaging with respect to the posterior Pe(· | s, a, z) is a convex combination and does not enlarge this error. The fixed-point perturbation argument used in the proof of Theorem 2 therefore gives γη γη b⋆ be ⋆ e ⋆ ∥Ve − Veℓ⋆ ∥∞ ≤ , ∥Q − Qℓ ∥∞ ≤ . 1−γ 1−γ The restriction of the empirical Bellman equation to dictionary windows is exactly equation 118. Thus Lemma 6 applies with the deterministic successor replaced by the posterior average. The same one-line replacement in the backward induction of Lemma 7 proves that equation 120 recovers the empirical action scores on every arbitrary window. Likewise, Lemma 8 is unchanged because posterior averaging is 1-Lipschitz. Consequently, γη e e K (s, e e ⋆ℓ (s, e + γ K+ℓ Vmax . (123) sup Q c, a) − Q c, a) ≤ V 1 − γ s,e c,a It is enough to take 1 32 log . (124) 1−γ ε(1 − γ) The choices in equation 122–equation 124 make the right-hand side at most ε(1 − γ)Vmax /2. Applying the approximate-greedy argument used in the proof of Theorem 2 proves equation 121. K≥
After the dictionary averages have been precomputed, one sweep of equation 118 costs O(n(nm + 1)N ℓ ) operations, and the backward extension costs O(ℓn(nm + 1)N ℓ ). Relative to the perfect planner, the posterior sum introduces only one additional factor n. 35
C.3
T HE NOISY VERSION OF DLA-UCB
Theorem 5 (Regret of N OISY-DLA-UCB). Assume equation 109– equation 110 and the stochastic reward model of Section 5. Fix the look-ahead depth ℓ. For every T ≥ 2 and δ ∈ (0, 1), with probability at least 1 − δ, the algorithm described below, N OISY-DLA-UCB, satisfies s ! 3 mT R n m max g ℓ (T ) = O eℓ Rmax n Reg . (125) + 1−γ (1 − γ)2 eℓ hides factors logarithmic in n, m, T, δ −1 , and (1 − γ)−1 , and constants depending only Here O on the fixed depth ℓ. For fixed ℓ, the algorithm has polynomial update time, representation size, and per-decision computation. Algorithmic modifications. The observed noisy entry no longer determines the physical successor. Relative to DLA-UCB, the learner must therefore estimate the conditional law of that successor given the current state, action, and noisy entry. A synthetic dictionary element must consequently contain two objects: a noisy table, which is appended to the look-ahead window, and, for every possible local context, a physical successor sampled from the corresponding estimated conditional law. These two objects jointly simulate the next augmented state. The reward estimates and their doubling schedule are unchanged. At an update based on the first N expired tables, define, for h = (s, a, z) ∈ S × A × S, kN (h) :=
N −1 X
n o e t (s, a) = z , 1 St = s, At = a, Θ
(126)
t=0
b PeN (s′ | h) :=
o PN −1 n ′ e 1 S = s, A = a, Θ (s, a) = z, S = s t t t t+1 t=0 kN (h)
,
kN (h) > 0.
(127)
b When kN (h) = 0, set PeN (· | h) to the uniform distribution. This choice is immaterial because the continuation estimate used at an unvisited context is clipped at Vmax . Every noisy table is observed in full. Its product law is therefore estimated from all expired tables as ! N −1 O X 1 b e N := Q δe . (128) N t=0 Θt (s,a) (s,a)∈S×A
This distribution can be sampled coordinatewise, without enumerating Ω. As in the perfect-look-ahead case, every planner update constructs a fresh dictionary. Set N 1 2N 2 MN := , K := log . N (1 − γ)3 1−γ 1−γ
(129)
Conditionally on the observations available at the update, independently for j = 1, . . . , MN , draw b eN , ej ∼ Q Z
b Y j (h) ∼ PeN (· | h) for every h ∈ S × A × S.
(130)
All draws in equation 130 are mutually independent conditional on the data. Thus, when the current local context is h, the jth simulated next augmented state uses Y j (h) as its physical state and Zej as the new table appended to the window. The rest of the implementation mirrors DLA-UCB. Value iteration is performed on S × [MN ]ℓ , with the compound successors in equation 130 replacing the deterministic successors of the perfectlook-ahead dictionary. At decision time, the same backward extension is applied to the observed noisy window. The exact optimistic continuation rule used in these backups is specified in the proof; no additional online exploration step is performed. 36
Algorithm 5 N OISY-DLA-UCB- UPDATE e 0:N −1 , transition and reward observations, preInput: Number N of expired tables, noisy tables Θ + vious reward bound rold , horizon T , confidence level δ Output: Planning object D b e N using equation 128 1: Compute Q 2: for every h ∈ S × A × S do b 3: Compute kN (h) and PeN (· | h) using equation 126–equation 127 4: end for 5: Update r + exactly as in Algorithm 3 6: Compute MN and KN from equation 129 7: Draw the compound dictionary according to equation 130 8: Construct the optimistic dictionary backup specified in the proof below 9: Initialize v 0 ≡ Vmax on S × [MN ]ℓ 10: for k = 0, . . . , KN − 1 do 11: Apply one optimistic dictionary Bellman backup to obtain v k+1 from v k 12: end for e1:MN , (Y 1:MN (h))h , v KN , r+ , kN ) 13: return D = (N, Z
Algorithm 6 N OISY-DLA-UCB- ONLINE Input: Horizon T , look-ahead depth ℓ, confidence level δ Output: Actions A0 , . . . , AT −1 1: Set D ← ∅ and r + (s, a) ← Rmax for every (s, a) e ℓ ) and play an arbitrary action A0 2: Observe X0 = (S0 , C 0 3: Observe (R0 , S1 ) and update the reward statistics and the conditional-transition statistics of e 0 (S0 , A0 )) h0 = (S0 , A0 , Θ 4: for t = 1, . . . , T − 1 do etℓ ) 5: Observe Xt = (St , C 6: if D = ∅, t is a power of two, or a reward or local conditional-transition count has just entered {1, 2, 4, . . .} then 7: Set N ← t e 0:N −1 , past observations, r+ , T, δ) 8: D ← N OISY-D OLAR - UPDATE(N, Θ 9: Extract the updated reward bound r+ from D 10: end if eℓ 11: Compute the action scores by backward extension from D to C t 12: Play an action maximizing these scores 13: Observe (Rt , St+1 ) and update the reward statistics and the conditional-transition statistics e t (St , At )) of ht = (St , At , Θ 14: end for The global table count, each of the nm reward counts, and each of the n2 m local conditionaltransition counts can enter {1, 2, 4, . . .} at most 1 + ⌈log2 T ⌉ times. Hence the number of planner updates is O(n2 m log T ). An update based on N observations costs ℓ O N nm + MN n2 m + KN n2 mMN , (131) ℓ and a backward extension costs O(ℓn2 mMN ) per decision. The planning object occupies 2 ℓ O(MN n m + nMN ) memory. As in the perfect case, these bounds use precomputed means and standard deviations over the last dictionary index.
C.3.1
P ROOF OF T HEOREM 5
We analyze the fixed point of the compound-dictionary operator used by the algorithm, rather than introducing an ideal optimistic fixed point on all of S × Ωℓ . The latter route would require a uniform concentration bound over all noisy suffixes and would lose the dimension dependence in equation 125. The proof instead establishes optimism only on the finite computation graph visited by the 37
core and the backward extensions. Stability then controls the dictionary-dependent fixed point away from that graph, and a separate lemma bounds the expected negative part of its gap to Veℓ⋆ . The reward argument is unchanged, so Lemma 16 will be used directly. The scalar monotonicity argument of Lemma 12 and the restriction and extension arguments of Lemmas 6–8 will also be reused below; replacing a deterministic successor by an average over compound successors does not affect those arguments. Confidence bookkeeping.
The number of planning epochs is deterministically bounded by E T := 2 + 1 + nm + n2 m 1 + ⌈log2 T ⌉ . (132)
Let
T Mmax := (1 − γ)3
(133)
and fix
128(ℓ + 1)T 3 E T n3 m(Mmax + 1)ℓ . (134) LT := max 1, ℓ, log δ For fixed ℓ, LT is logarithmic in the problem parameters. Its slack covers all union bounds below; the precise numerical constant is irrelevant. Lemma 22 (Posterior sample streams). Conditionally on the complete noisy-table sequence e t )t≥0 , the successors observed on successive visits to a fixed h = (s, a, z) are independent with (Θ common law Pe(· | h). The statement remains true after conditioning on synthetic noisy tables sampled independently of the latent successors. Proof. By equation 114, conditional on the noisy tables and the past, the unrevealed coordinate e t (s, a)). Whether the algorithm visits h at time t is decided before this Θt (s, a) has law Pe(· | s, a, Θ coordinate is revealed. Optional skipping of the conditionally independent latent coordinates gives the claimed i.i.d. stream. Independent synthetic noisy tables do not alter this conditional law. The following comparison is deliberately coordinatewise. It will be applied to functions selected after seeing the data. Lemma 23 (Uniform posterior comparison). With probability at least 1 − δ/8, simultaneously for every update, every local context h, every d : S → [0, Vmax ], and every η ∈ (0, 1], CVmax nLT b . PeN (· | h) − Pe(· | h) d ≤ η Pe(· | h)d + η(1 ∨ kN (h))
(135)
The inequality remains valid when d is data-dependent. Proof. By Lemma 22, scalar Bernstein and a union bound over h, s′ , and all possible local sample counts give s 2Pe(s′ | h)LT 2LT be P N (s′ | h) − Pe(s′ | h) ≤ + . 1 ∨ kN (h) 3(1 ∨ kN (h)) This event is coordinatewise and hence uniform over d. Multiplication by d(s′ ), summation over s′ , Cauchy–Schwarz, and Young’s inequality give equation 135. For an update using N expired tables, set ( r qN := min 1,
n2 m log(N + 1) + LT 2N
) .
(136)
Lemma 24 (Uniform control of the noisy-table law). With probability at least 1 − δ/8, simultaneously for every sample size used by the algorithm, b e e H QN , Q ≤ qN . (137) 38
Consequently, for every possibly data-dependent f : Ω → [0, Vmax ], q √ 2 E be f − EQ VarQ e f ≤ 2 2qN e (f ) + 2Vmax qN , QN q q Var be (f ) − VarQ e (f ) ≤ 2Vmax qN . QN
(138) (139)
Proof. For one N , the method of types and product tensorization give 2 b e e P KL QN Q > x ≤ (N + 1)n m e−N x . Use 2H 2 ≤ KL and take a union bound over N ≤ T . The definition of qN and the slack in LT prove equation 137. The deterministic Hellinger mean and standard-deviation inequalities proved in Lemma 11 then give equation 138– equation 139. We next identify the finite collection on which scalar Bernstein confidence is required. This construction is used only in the proof. Condition on the complete noisy-table sequence and, for every b e N . For N ∈ {1, . . . , T }, pre-sample the noisy-table part Ze1:MN of a possible dictionary from Q N
every t < T , every k ∈ {0, . . . , ℓ}, and every (i0 , . . . , ik−1 ) ∈ [MN ]k , include the window e t+k , . . . , Θ e t+ℓ−1 , Zei0 , . . . , Z eik−1 Θ N N
(140)
in GT , with the first block empty when k = ℓ. Thus GT contains every observed window, every dictionary window, and every hybrid window used by any possible backward extension. Moreover, |GT | ≤ (ℓ + 1)T 2 (Mmax + 1)ℓ .
(141)
Crucially, GT depends on the noisy tables and the synthetic noisy-table draws, but not on the observed posterior-successor streams or the synthetic successors Y j (h). Pre-sampling is only a coupling device; the algorithm draws and reveals a dictionary only when an update occurs. For h = (s, a, z), define, when first needed, e Ph := Pe(· | h) ⊗ Q,
b be e bN,h := P P N (· | h) ⊗ QN .
(142)
These are the true and estimated conditional laws of the physical successor and the fresh noisy table. Also set ) ( s LT . (143) aN (h) := min 1, 1 ∨ kN (h) Lemma 25 (Confidence for optimal continuations on the relevant graph). With probability at least 1 − δ/8, simultaneously for every update, every h, every e c ∈ GT , and the continuation ′ ⋆ ′ e V (s , ze) := Vℓ (s , e c1:ℓ−1 , ze), we have h q EPbN,h V − EPh V ≤ C (aN (h) + qN ) VarPbN,h (V ) i + Vmax (aN (h) + qN )2 , and
q
VarPbN,h (V ) −
p VarPh (V ) ≤ CVmax (aN (h) + qN ).
(144) (145)
Proof. Fix h and e c ∈ GT . Conditional on the noisy tables and on the synthetic noisy tables that occur in e c, the continuation is fixed with respect to the posterior sample stream. We use the following elementary conditional-mixture version of scalar empirical Bernstein. If S1 , . . . , Sk are i.i.d. from p, pb is their empirical law, K is a fixed Markov kernel, and f ∈ [0, Vmax ], then q 2 |b pKf − pKf | ≤ C a VarpbK (f ) + Vmax a , q
VarpbK (f ) −
q VarpK (f ) ≤ CVmax a,
39
p with the usual empirical-Bernstein probability, where a = 1 ∧ x/(1 ∨ k). The first inequality follows by applying scalar empirical Bernstein to s′ 7→ Kf (s′ ) and observing that Varpb(Kf ) ≤ VarpbK (f ). For the second, apply Bernstein to s′ 7−→ K (f − pKf )2 (s′ ). 2 Its variance is at most Vmax VarpK (f ); the identity Var(f ) = inf c pK[(f − c)2 ], used in both directions, then gives the displayed standard-deviation comparison.
b b e N . It controls the first Apply this fact conditionally with p = Pe(· | h), pb = PeN (· | h), and K = Q step in b b b e N −→ Pe ⊗ Q e N −→ Pe ⊗ Q e PeN ⊗ Q with coefficient aN (h). For the second step, tensoring both noisy-table laws with the same posterior leaves their Hellinger distance unchanged. Hence Lemma 24 controls its mean and standard deviation with coefficient qN . The triangle inequality and (aN (h) + qN )2 ≥ 2aN (h)qN give equation 144– equation 145. The union bound is over local contexts, possible local sample counts, and the graph in equation 141; it is covered by LT . The compound-dictionary operator. We now give the continuation rule referred to in Algorithms 5– 6. Write D for the collection of compound samples in equation 130. At an update based on N observations, define ( r ) LT dN := min 1, , λN (h) := min 1, c0 aN (h) + qN + dN , (146) MN where c0 is a sufficiently large universal numerical constant. For y = (y1 , . . . , yMN ) ∈ [0, Vmax ]MN , let v u MN MN u 1 X 1 X y := yj , s(y) := t (yj − y)2 , MN j=1 MN j=1 and set
D UN (y; h) := min Vmax , y + max 7λN (h)s(y), 49Vmax λ2N (h)
.
(147)
For a core array v : S × [MN ]ℓ → [0, Vmax ], a core state x = (s, i0 , . . . , iℓ−1 ), and a ∈ A, put ei0 (s, a) , hx (a) := s, a, Z yj (v; x, a) := v Y j (hx (a)), i1 , . . . , iℓ−1 , j . The Bellman update used by Algorithm 5 is D,+ (TeN,r + v)(x) n o D N := max min Vmax , r+ (s, a) + γUN (yj (v; x, a))M ; h (a) . x j=1 a∈A
(148)
For completeness, its backward extension to an arbitrary observed window e c = (θe0 , . . . , θeℓ−1 ) is defined as follows. Set N,D,v Uℓ,e (s, i0 , . . . , iℓ−1 ) := v(s, i0 , . . . , iℓ−1 ). c
(149)
For k = ℓ − 1, . . . , 1, let N,D,v Uk,e (s, i0 , . . . , ik−1 ) c MN N,D,v D j := max min Vmax , r+ (s, a) + γUN Uk+1,e Y (h), i , . . . , i , j ; h , (150) 0 k−1 c a∈A
j=1
where h = (s, a, θek (s, a)) in this display. Keeping the root action fixed gives the deployed score e D,v+ (s, e Q c, a) N,r MN N,D,v + D j := min Vmax , r (s, a) + γUN U1,ec Y (h), j ;h , j=1
40
(151)
where now h = (s, a, θe0 (s, a)). It is useful to give a semantic, index-free representation of the same operator. For W : S × Ωℓ → [0, Vmax ], define D,+ (BeN,r c) + W )(s, e M N + D j j e e e ;h , := max min Vmax , r (s, a) + γUN W Y (h), θ1 , . . . , θℓ−1 , Z a∈A
j=1
(152)
D where h = (s, a, θe0 (s, a)). The scalar argument in part 1 of Lemma 12 shows that UN (·; h) is nondecreasing in every coordinate and is 1-Lipschitz in supremum norm. Therefore both equation 148 and equation 152 are monotone γ-contractions.
Let WND be the fixed point of equation 152. The proofs of Lemmas 6 and 7 apply verbatim to the compound samples: the restriction of WND to dictionary windows is the fixed point of equation 148, and equation 149– equation 151, initialized with that core fixed point, recovers WND and its action scores on every explicit window. By Lemma 8, using v KN instead changes every deployed action score by at most γ KN Vmax . Hence the action selected by the algorithm is 2γ KN Vmax -greedy for the exact dictionary scores. We next verify optimism only where it is needed. For a continuation V of Veℓ⋆ at a graph window and a local context h, write D
V N :=
MN 1 X V (Y j (h), Zej ), MN j=1
D ej ))MN , σN (V ) := s (V (Y j (h), Z j=1
with the fixed suffix suppressed. Lemma 26 (Dictionary concentration on the relevant graph). With probability at least 1 − δ/8, simultaneously for every update, every graph continuation of Veℓ⋆ , and every h, D
D EPbN,h V ≤ V N + 3dN σN (V ) + CVmax d2N ,
q D σN (V ) − VarPbN,h (V ) ≤ CVmax dN .
(153) (154)
Proof. A graph continuation contains at most ℓ noisy tables drawn from the same dictionary. Fix their indices, condition on the corresponding compound samples, and omit those indices from the bN,h , and the continuation is now fixed. empirical mean. The remaining pairs are i.i.d. with law P The empirical Bernstein inequality and Lemma 14 give equation 153– equation 154 for the reduced sample. Restoring at most ℓ p observations changes the mean by at most ℓVmax /MN and the standard deviation by at most 2Vmax ℓ/MN . Since LT ≥ ℓ, these errors are absorbed by CVmax d2N and CVmax dN , respectively. If MN ≤ 2ℓ, the result is immediate after increasing C. A union bound over the index tuples, local contexts, and possible updates is covered by equation 134. Lemma 27 (Optimism on the relevant computation graph). On the events of Lemmas 25 and 26, if r+ ≥ r pointwise, then W D (s, e c) ≥ Ve ⋆ (s, e c) for every s ∈ S and e c ∈ GT . (155) N
ℓ
D (·; h) = Vmax . Otherwise, equation 144 and equation 153– equaProof. If λN (h) = 1, then UN tion 154, together with the choice of the universal constant c0 , imply D N UN (V (Y j (h), Zej ))M (156) j=1 ; h ≥ EPh V
for every graph continuation V of Veℓ⋆ . Here one uses the same elementary domination max{7x, 49y} ≥ 2x + 5y as in the proof of Lemma 12. Dictionary windows are closed under the sampled dynamics. Applying equation 156 on this finite core and using monotonicity and contraction proves fixed-point optimism on the core, exactly as in Lemma 13. Starting from the core and proceeding backward through equation 150 proves the same claim successively for every hybrid window in equation 140, including the observed window at the root. This proves equation 155 without asserting optimism on any other window. 41
Stability and the off-graph negative part. Graph optimism alone is insufficient in a one-step conditional expectation: the true continuation law may assign mass to windows outside GT . We next control this mass through stability of the deployed fixed point. Lemma 28 (Stability on explicit windows). Let D and D′ be two compound dictionaries that differ in one compound sample, while the estimated model, reward estimate, and coefficients are held fixed. Then ′ 2γVmax βN := WND (s, e c) − WND (s, e c) ≤ βN , sup . (157) (1 − γ)MN (s,e c)∈S×Ωℓ This comparison concerns the same explicit window under the two dictionaries; it does not compare equal index tuples, whose semantic windows change when a dictionary table is replaced. Proof. Fix h and consider the unclipped expression in equation 147. On the constant branch of the maximum, changing one coordinate changes it by at most Vmax /MN . On the variance branch, s(y) ≥ 7Vmax λN (h) and, whenever s(y) > 0, ∂s(y) |yj − y| = . ∂yj MN s(y) The contribution of the variance term to the derivative is therefore at most 1/MN . Continuity at the D branch boundary and clipping show that changing one coordinate of y changes UN (y; h) by at most 2Vmax /MN . Let ∆ denote the supremum on the left-hand side of equation 157. If the two dictionaries differ in their jth compound sample, then every continuation coordinate other than j changes by at most ∆, whereas the jth coordinate may change by at most Vmax . The 1-Lipschitz property and the preceding single-coordinate bound, applied to the two explicit Bellman equations equation 152, give ∆ ≤ γ∆ +
2γVmax . MN
Rearranging proves equation 157. Define, at the point where they are needed, r CVmax LT gN := , 1−γ MN
sN := CVmax
LT (1 − γ)2 MN
1/4 .
(158)
Lemma 29 (Stable generalization of deployed continuations). With probability at least 1 − δ/8, simultaneously at every update, for every actually observed window e c = (θe0 , . . . , θeℓ−1 ) and every h, MN 1 X WND Y j (h), θe1:ℓ−1 , Zej MN j=1 D ′ e e − E(S ′ ,Z)∼ e P bN,h WN S , θ1:ℓ−1 , Z
≤ gN ,
(159)
MN D j j e e s WN Y (h), θ1:ℓ−1 , Z j=1 r e + sN . ≤ Var b W D (S ′ , θe1:ℓ−1 , Z)
(160)
and
PN,h
N
The mean bound equation 159 also holds after replacing WND by [Veℓ⋆ − WND ]+ . Proof. Treat the jth compound draw (Zej , (Y j (h))h ) as one training sample. For a fixed observed suffix, let FD (ξ) be the corresponding continuation of WND evaluated at a fresh compound sample 42
ξ. By Lemma 28, replacing one training sample changes FD (ξ), uniformly in ξ, by at most βN . The usual ghost-sample replacement argument therefore gives MN X 1 ED Eξ FD (ξ) − FD (ξj ) ≤ βN . MN j=1 Replacing one training sample changes the quantity in brackets by at most 2βN + Vmax /MN . McDiarmid’s inequality and the union bound encoded by LT hence give Eξ FD (ξ) −
p MN p 1 X Vmax FD (ξj ) ≤ C √ + βN MN LT ≤ gN . MN j=1 MN
The positive-part map is 1-Lipschitz, so the same argument applies to the stated loss. 2 2 Apply the argument once more to FD ] and its stability is at most 2Vmax βN . . Its range is [0, Vmax Thus its empirical and population second moments differ by at most r 2 CVmax LT . 1−γ MN √ √ Combining this with the mean bound, the identity Var(F ) = EF 2 − (EF )2 , and | x − y| ≤ p |x − y| proves equation 160.
Lemma 30 (Expected off-graph negative part). Fix a planning object, a state-window pair x = (s, e c) actually observed while it is active, and an action a. Let h = (s, a, θe0 (s, a)), set G = D WN − Veℓ⋆ , and write G− = (−G)+ . Then Vmax nLT ′ 2 e EPh G− S , e c1:ℓ−1 , Z ≤ C gN + Vmax qN + . (161) 1 ∨ kN (h) Proof. For every j, the compound continuation (Y j (h), e c1:ℓ−1 , Zej ) is a hybrid graph state. Lemma 27 therefore gives MN 1 X ej = 0. G− Y j (h), e c1:ℓ−1 , Z MN j=1
bN,h by gN . The loss version of Lemma 29 bounds the expectation of this loss under P Next replace the estimated noisy-table marginal by the √ true one. Applying equation 138 condi2 tionally on the successor state, averaging, and using qN Vmax x ≤ x/4 + CVmax qN bounds the 2 resulting expectation by C(gN + Vmax qN ). Finally apply Lemma 23 with η = 1/2 to the nonnegative function obtained after averaging over the true noisy-table marginal. Absorbing the resulting half of the target expectation proves equation 161. One-step recursion and deterministic sums. At time t ≥ 1, let Nt be the sample size stored in the active planning object and let kt (h) := kNt (h). Let Wt be the exact extended fixed point of that planning object and set Dt := Wt − Veℓ⋆ . After At is selected, define e t (St , At ) , ht := St , At , Θ
λt := λNt (ht ).
Conditionally on Ft , which contains the history and the current noisy window before At is selected, put pt := E[(Dt )+ (Xt+1 ) | Ft ], σt2 := Var Veℓ⋆ (Xt+1 ) | Ft .
vt := E[(Dt )− (Xt+1 ) | Ft ], (162) 43
Lemma 31 (Noisy one-step recursion). On the joint confidence event, the action selected by Algorithm 6 satisfies e ⋆ℓ (Xt , At ) Dt (Xt ) + Veℓ⋆ (Xt ) − Q ≤ rt+ (St , At ) − r(St , At ) + 2γ KNt Vmax + γ(pt − vt ) " p p + Cγ λt σt + λt Vmax pt + λt Vmax vt + Vmax λ2t # Vmax nLT γ(1 − γ) + + gNt + λt sNt + (pt + vt ). (1 − γ)(1 ∨ kt (ht )) 32 (163) Proof. The restriction and extension identities, contraction, and the choice of KNt imply that the selected action is 2γ KNt Vmax -greedy for the exact dictionary scores. Repeating the first Bellman comparison in the proof of Lemma 18 gives e ⋆ (Xt , At ) Dt (Xt ) + Veℓ⋆ (Xt ) − Q ℓ ≤ rt+ (St , At ) − r(St , At ) + 2γ KNt Vmax h i D eℓ⋆ (Xt+1 ) , + γ UN (W ; h ) − E V t t P h t t D (Wt ; ht ) denotes equation 147 applied to the continuations of Wt from the current obwhere UN t served suffix. Adding and subtracting EPht Wt (Xt+1 ) produces exactly pt − vt .
It remains to control the width of the sampled continuation rule at the dictionary-dependent value Wt . Write Wt = Veℓ⋆ + Dt . For the first term, use Lemma 25; for the empirical mean and standard deviation of Wt , use Lemma 29. For the signed difference Dt , apply Lemma 23 separately to (Dt )+ and (Dt )− , and apply equation 138 to the noisy-table marginal. Taking the parameter in equation 135 to be a sufficiently small universal multiple of 1 − γ gives 1−γ (pt + vt ) EPbN ,h Dt − EPht Dt ≤ t t 32 p Vmax nLT 2 + C qNt Vmax (pt + vt ) + Vmax qN . + t (1 − γ)(1 ∨ kt (ht )) (164) The same comparisons, now applied to |Dt | with a constant parameter, give " q p p VarPbN ,h (Dt ) ≤ C Vmax pt + Vmax vt + Vmax qNt t
t
s + Vmax
# nLT . 1 ∨ kt (ht )
Together with equation 145 and the triangle inequality for standard deviations, these bounds imply D UN (Wt ; ht ) − EPht Wt (Xt+1 ) t " p p ≤ C λt σt + λt Vmax pt + λt Vmax vt + Vmax λ2t
# Vmax nLT 1−γ + + gNt + λt sNt + (pt + vt ). (1 − γ)(1 ∨ kt (ht )) 32 Here qNt ≤ c−1 0 λt whenever λt < 1, while the case λt = 1 is immediate from boundedness; also, s nLT nLT λt ≤ λ2t + . 1 ∨ kt (ht ) 1 ∨ kt (ht ) Substitution proves equation 163. 44
Lemma 32 (Cumulative noisy confidence terms). For fixed ℓ, T −1 X
eℓ (n2 m), λ2t = O
(165)
nLT eℓ (n3 m), =O 1 ∨ k (h ) t t t=1
(166)
t=1 T −1 X
s
T −1 X
! T eℓ Rmax gNt = O , 1−γ t=1 √ T −1 1/4 X eℓ Rmax n m T , λt sNt = O (1 − γ)3/4 t=1 s ! T −1 X Rmax n3 m T e + . vt = Oℓ Rmax 1−γ 1−γ t=1
(167)
(168)
(169)
Proof. The global power-of-two updates imply t/2 ≤ Nt ≤ t. If a local context is visited J times, its doubling schedule gives J X 1 ≤ C(1 + log J), 1 ∨ kj j=1 where kj is the frozen count used on its jth visit. Summing over the n2 m contexts proves equation 166 and controls the contribution of a2Nt (ht ) to equation 165. Moreover, X X 2 e 2 m), eℓ (1), qN = O(n d2Nt = O t t<T
t<T 3
because Nt ≥ t/2 and MN ≥ N/(1 − γ) . This proves equation 165. √ P −1/2 The definition of gN and t<T Nt = O( T ) give equation 167. Furthermore, r (1 − γ)LT 2 2 sN ≤ CVmax , N so Cauchy–Schwarz and equation 165 give equation 168. Finally, Lemma 30, applied along the trajectory, gives Vmax nLT 2 vt ≤ C gNt + Vmax qNt + . 1 ∨ kt (ht ) Summing this inequality and using the preceding bounds proves equation 169. Completion of the proof of Theorem 5. Invoke the preceding events, the reward event of Lemma 16, the predictable-to-realized event of Lemma 19, and the discounted total-variance event of Lemma 20, with confidence budgets whose sum is at most δ. The first decision contributes at most Vmax . By Lemma 27, Dt (Xt ) ≥ 0 at every actually observed window. Apply Lemma 19 to the nonnegative random variable Yt := (Dt )+ (Xt+1 ), E[Yt | Ft ] = pt . On the graph-optimism event, the realized successor window also belongs to GT , so Yt = Dt (Xt+1 ) along the trajectory. Within a planning epoch {p, . . . , q}, Dt is fixed and therefore q X
Yt − Dt (Xt ) = Dt (Xq+1 ) − Dt (Xp ) ≤ Vmax .
t=p
Use Young’s inequality in the positive adaptive term: p 1−γ CVmax λ2t Cγλt Vmax pt ≤ pt + . 16 1−γ 45
(170)
Together with the explicit (1 − γ)pt /32 term in equation 163, the coefficient of pt remains at most 1 − c(1 − γ) for a universal c > 0. Thus Lemma 19 and equation 170 yield the same epoch potential bound as in Lemma 21. The negative contribution γ(1 − γ) vt 32 is nonpositive and can be discarded. Summing equation 163 therefore gives " T −1 −1 X TX g Regℓ (T ) ≤ C rt+ (St , At ) − r(St , At ) + γλt σt −γvt +
t=0
+
+
t=1 T −1 X
T −1 X
Vmax nLT 1 Vmax λ2 + 1 − γ t=1 t 1 − γ t=1 1 ∨ kt (ht ) T −1 X
−1 p TX gNt + λt sNt + λt Vmax vt
t=1
t=1
# Vmax LT + Rmax . + Vmax E T + 1−γ
(171)
Indeed, the value-iteration errors are summable because γ KN Vmax ≤
Rmax . 2N 2
Lemma 20 uses only the Bellman equation and the filtration of the augmented Markov process. It therefore applies verbatim to the noisy augmented process and gives T −1 X
h i 2 g ℓ (T ) + Vmax γ 2 σt2 ≤ C Vmax Rmax T + Vmax Reg LT .
(172)
t=1
Consequently, by Cauchy–Schwarz and equation 165, ! r T −1 h i X eℓ g ℓ (T ) . γλt σt ≤ O n2 m Vmax Rmax T + Vmax Reg t=1
The self-bounding term is absorbed through q g ℓ (T ) + CVmax n2 m. g ℓ (T ) ≤ 1 Reg C n2 mVmax Reg 4 It remains to verify that the off-graph contribution is lower order. Lemma 32 and Cauchy–Schwarz give v ! u T −1 X X u X p 2 t λt Vmax vt ≤ λ Vmax vt t
t
t=1
√
t 1/4
eℓ Rmax n m T ≤O (1 − γ)3/4
Rmax n5/2 m + 1−γ
.
(173)
If T ≥ (1 − γ)−1 , the first term in equation 173 is bounded by the leading term in equation 125; if T < (1 − γ)−1 , it is bounded by the lower-order term. The second term is also bounded by the lower-order term because n ≥ 1 and 1 − γ ≤ 1. The same case split controls equation 168, while equation 167 is smaller still. Finally substitute Lemma 16, Lemma 32, and equation 132 into equation 171, use Vmax = Rmax /(1 − γ), and absorb the preceding quarter of the regret. The leading term is s ! p mT 2 e e Oℓ n mVmax Rmax T = Oℓ Rmax n , 1−γ 46
and the largest lower-order contribution is Vmax n3 m Rmax n3 m e e Oℓ . = Oℓ 1−γ (1 − γ)2 This proves equation 125.
47