Scale-free adaptive planning for deterministic dynamics & discounted rewards

Approach

• PlaTγPOOS uses a scale-free function-optimization strategy rather than upper-confidence bounds, adapting without prior knowledge of noise or reward ranges.The approach is based on Bartlett et al. (2019) and is presented as an alternative to OLOP.Source: §1 · pp. 1–2

Problem setting

• The objective is to recommend the best first action under a fixed interaction budget, minimizing simple regret rather than cumulative regret during search.After the agent takes that action, the evaluation can be repeated from the next state with a new budget.Source: §1 · p. 1

Approach

• Discounting by γ brings smoothness to the value function, which the planning strategy exploits while adapting to unknown noise and reward ranges.The algorithm can also adapt to additional global smoothness beyond that supplied by γ.Source: §1 · p. 2

Contributions

• The algorithm adapts its behavior to reward and noise ranges, avoiding failure when ranges are underestimated and improving efficiency when they are overestimated.The paper says it recovers OLOP's results while allowing improvements in various problem classes.Source: §1 · p. 2
• PlaTγPOOS adapts to unknown reward ranges, noise without prior knowledge, and additional global smoothness; the paper reports faster empirical learning than UCB approaches.It also obtains fast rates for deterministic planning across all regimes, including exponentially faster learning than OLOP when there is no noise.Source: §1 · p. 2

Scope

• The results apply to MDPs with deterministic dynamics and can also be applied to open-loop planning over action sequences.The setup considers a realistic reset constraint: the agent can reset only to the original state.Source: §1 · p. 2

2. Background

• The setting has deterministic transitions, noisy rewards, a finite action set, and a known discount factor; the objective is to recommend a best next action using a generative model and limited budget.The rewards are assumed to lie in [0, Rmax], and the state space may be large or infinite.Source: §2 · p. 2, §2.1 · p. 3

2.1. Optimistic planning under finite numerical budget

• The performance loss measures how far the recommended first action falls short of the optimal first action, with optimal continuation after either choice.The planning objective is evaluated as simple regret rather than penalizing suboptimal actions queried during search.Source: §2.1 · p. 3

2.2. The planning tree

• The planning tree has one node for each finite action sequence from the initial state, and deterministic dynamics associate each sequence with a reachable state.The branching factor is the number of available actions.Source: §2.2 · p. 3
• For a finite sequence, u and b provide lower and upper bounds on its value; the algorithm expands nodes using generative-model evaluations.The number of openings, rather than evaluations, is used for the stated budget bounds, and evaluations are at most K times the openings.Source: §2.2 · p. 3
• The value-function smoothness condition bounds the gap between a sequence's value and its lower bound by νρ^h at depth h, with the default choice ν = Rmax/(1 − γ) and ρ = γ.Extra regularity may permit smaller ν and ρ, and the results adapt to ρ without knowing it.Source: §2.2 · p. 3
• The paper introduces κu(ν, ρ), based on near-optimal lower-bound sequences, and states that its results recover earlier κv(ν, γ)-based results while extending beyond the earlier ρ = γ formulation.Proposition 2 relates the quantities by κu(ν/2, γ) ≤ κv(ν, γ) ≤ κu(2ν, γ).Source: §2.2 · p. 4

3. Optimization vs. planning

• The planning approach is a close relative of StroquOOL, but its design accounts for discounted rewards and the planning setting’s structure.The paper compares naïve and good planning strategies through the uncertainty of their value estimates.Source: §3 · p. 4
• Planning reuses reward samples across distinct action sequences when they share a prefix, concentrating estimates more efficiently than estimating each sequence from its own episode.This cross-sequence sharing is the “good” planning strategy contrasted with the naïve strategy.Source: §3 · p. 4
• Uniform exploration can sample all K^Hu nodes at shallow depth Hu, while selective methods explore a smaller promising subset to greater depth Hs.For selective strategies, the number of deeper sequences containing a given subsequence can be difficult to bound.Source: §3 · p. 4
• PlaTγPOOS enforces that a node at depth h + 1 is pulled γ² times less often than one at depth h, supporting its concentration analysis.The paper leaves open whether direct StroquOOL application to planning can achieve equivalent theoretical guarantees.Source: §3 · p. 4

4. Deterministic dynamics and rewards

• The section first simplifies the analysis to deterministic rewards, where evaluations are noiseless.The passage specifies ε_t = 0 and r_t = r(x_t, a_t).Source: §4 · p. 4
• SequOOL applied to planning achieves the same simple-regret rates as OPD in the doubly deterministic case, up to logarithmic factors.It also avoids using Rmax and adapts to extra smoothness in the value function.Source: §4 · p. 4
• With resets, reaching a node before opening it costs h(a), leaving O(n/h²) nodes open at depth h rather than O(n/h).The maximum depth falls from order n to order √n under the stated budget.Source: §4 · p. 5
• For κ > 1, the reset condition changes simple regret by no more than numerical constants.The passage says exponentially diminishing simple regret remains, but its displayed rate is incomplete in the supplied text.Source: §4 · p. 5

5. Deterministic dynamics, stochastic rewards

• With stochastic rewards, PlaTγPOOS evaluates cells repeatedly rather than fixing the evaluation count, trading deeper exploration for more accurate mean estimates.Discounting reduces the weight of rewards deeper in the tree, which the algorithm uses when allocating evaluations across depths.Source: §5 · p. 5

5.1. Analysis of PlaTγPOOS

• Theorems 3 and 4 state simple-regret bounds for PlaTγPOOS in high- and low-noise regimes; Table 1 summarizes upper-bound rates across problem classes and noise conditions.Source: §5.1 · p. 6, Table 1 · p. 7
• PlaTγPOOS adapts to unknown noise range b, with bounds scaling as n/b² in standard high-noise cases; OLOP's rate can suffer when its input estimate eb ≫ b.The analysis also identifies low-noise conditions where PlaTγPOOS obtains improved rates.Source: §5.1 · p. 7
• At very low noise, PlaTγPOOS recovers deterministic OPD rates n^-log(1/ρ)/logκ or ρn, unlike OLOP's O(1/√n).For κ = 1, the analysis also reports exponentially decreasing simple regret; PlaTγPOOS can explore to depth order n, typically order √n under sampling limits, versus OLOP's log n.Source: §5.1 · p. 7
• In most cases, PlaTγPOOS's rate uses value-function smoothness ρ where OLOP's rate uses γ, adapting to smoothness beyond that supplied by discounting.The paper treats this adaptation across a large portion of cases.Source: §5.1 · p. 7
• The reset condition leaves polynomial rates unchanged but changes exponential rates; a ρ^n rate becomes ρ… when the condition is absent.The passage does not provide the full expression for the changed rate.Source: §5.1 · p. 7

6. Numerical experiments

• The experiment uses a deterministic two-action MDP whose state is a binary variable and a non-negative integer.When the chosen action matches the binary state, reward grows with the integer; otherwise, the next state resets the integer to zero.Source: §6 · p. 8
• The experiment uses γ = 0.95 and reports cumulative discounted returns after 20 interaction steps.At each step, the agent follows its planning strategy’s recommended action and transitions to the resulting state.Source: §6 · p. 8
• PlaTγPOOS systematically outperforms OLOP across tested noise ranges, even when OLOP receives the correct Rmax and noise-range inputs.The reported returns exclude the fixed reward shift of 100.Source: §6 · p. 8
• OLOP’s performance is vulnerable to misspecified inputs, while PlaTγPOOS does not use those inputs.The comparison is shown for misleading OLOP parameters in Figure 4.Source: §6 · p. 8

A. On the branching factor

• Proposition 2 bounds κv(ν, γ) between κu(ν/2, γ) and κu(2ν, γ).Source: A. On the branching factor · p. 10
• The total opening budget is at most n + 1, including the final cross-validation evaluation.The text notes that n + 1 is used for notational convenience and that the evaluation could instead use n/4 to fit under n.Source: B. PlaTγPOOS is not using a budget… · p. 10
• The number of openings is linear in n.The section bounds depth-exploration openings by n + 1 before accounting for the additional final evaluation.Source: B. PlaTγPOOS is not using a budget… · p. 10

C. Proofs of the lemmas

• With probability at least 1 − δ, all reward-average estimates for evaluated state-action pairs lie within their confidence intervals.The event is defined over the sequence of action choices evaluated during a run.Source: C. Proofs of the lemmas · p. 10
• The proof uses Azuma-Hoeffding concentration with a union bound because each execution requires controlling only polynomially many estimators.The estimator count is contrasted with the potentially exponential number of cells that could be evaluated.Source: C. Proofs of the lemmas · p. 11
• Lemmas 1 and 3 give sufficient conditions for reaching depth h at a given p, with Lemma 3 applying on event ξ.The proof of Lemma 3 proceeds by induction over depths.Source: C. Proofs of the lemmas · pp. 11–12

D. Proof of Theorem 3 and Theorem 4

• In the high-noise regime, Theorem 3 states a simple-regret bound after n rounds for problems with associated (ν, ρ) and branching factor κ = κu(ν, ρ).The regime requires the noise b to satisfy both high-noise conditions defined in Table 1’s caption.Source: D. Proof of Theorem 3 and Theorem 4 · p. 13
• In the low-noise regime, Theorem 4 states a simple-regret bound for PlaTγPOOS.The passage specifies that b must be low enough to verify both high-noise conditions as defined in the caption of Table 1.Source: D. Proof of Theorem 3 and Theorem 4 · p. 14
• The proofs bound simple regret on event ξ, whose probability is at least 1 − δ.Source: D. Proof of Theorem 3 and Theorem 4 · p. 14

• The depth and sample-count choices target the fewest samples and greatest depth for which the bound conditions hold, found by solving where the inequalities become equalities.Source: Step 1) General definition of the regret · p. 14
• When γ^2κ ≤ 1, the equation can have two solutions: the largest may fail Equation 5, while the smallest may be difficult to express in closed form.The analysis therefore defines the parameters separately for this regime.Source: Step 1) General definition of the regret · p. 15
• Low-range noise is treated separately because it can yield a regret rate close to the deterministic case.Source: Step 1) General definition of the regret · p. 15
• The resulting rate is not better than the deterministic rates in the analyzed case.Source: Step 1) General definition of the regret · p. 16

• Floor functions can make the budget used in practice significantly smaller than n, affecting bound constants but noticeably influencing performance.Source: E. Use of the budget · p. 20
• The budget can be optimized by scaling hmax while staying within n and accounting for the fact that pulls at depth h cannot exceed Kh.Source: E. Use of the budget · p. 20