PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning with Multi-Step Transition Predictions: A Bellman Theory

Chenbei Lu, Zaiwei Chen, Tongxin Li, Chenye Wu, Adam Wierman

arXiv:2610.32887v1cs.LG

TL;DR

Directly augmenting an MDP state with multi-step predictions can create an exponentially large state space, while the value of predictive information remains difficult to quantify. The paper analyzes discounted finite MDPs under block feedback using a Bayesian Bellman equation on the original state space and proposes BF–BOLA for learning near-optimal policies. It shows that prediction coverage reduces transition learning to uncovered rows and that policy learning can require fewer prediction samples than Bayesian value estimation.

  • Problem

    Directly incorporating multi-step predictions can cause exponential state-space growth and make dynamic programming computationally expensive, while their decision value is difficult to quantify.

    Source: §1 · p. 2

  • Method

    The paper studies block feedback, derives a Bayesian Bellman equation on the original state space, and proposes BF–BOLA for learning near-optimal policies.

    Source: §1 · p. 2, §1.1.1 · p. 2, §1.1.3 · p. 3

  • Results

    Prediction coverage reduces transition learning to uncovered rows, and learning a near-optimal policy can require fewer prediction samples than estimating the Bayesian value function.

    Source: §7 · pp. 20–21

  • Takeaways & Limitations

    The Bayesian value remains on the original state space even when policies use high-dimensional prediction information online.

    Source: §1.1.1 · p. 2

    The analysis concerns block feedback; extending equally sharp low-dimensional representations to richer receding-horizon protocols remains open.

    Source: §7 · p. 21

Abstract

from arXiv · show

Multi-step predictions of future transition realizations can improve reinforcement learning, but their value remains difficult to quantify. Directly including these predictions in the state can lead to exponential state-space growth, making direct dynamic programming computationally expensive. We study discounted finite MDPs under a block-feedback protocol: at the start of each K-period block, the decision maker observes $K$-step probabilistic transition predictions for a subset of actions and adapts decisions to observed states within the block. We show that the optimal value satisfies a Bayesian Bellman equation on the original state space. This representation reveals that predictive information creates value by recursively changing the local order of maximization and expectation in the Bellman expansion. We formalize this effect through a Bellman--Jensen analysis and quantify the effects of prediction horizon, error, action coverage, and within-block feedback. We propose block-feedback Bayesian offline learning with online adaptation (BF--BOLA), a model-based algorithm for learning near-optimal policies, and establish upper and lower sample-complexity bounds that match up to logarithmic factors in the stated regimes. The results show that predictions can reduce transition learning to uncovered rows and that learning a near-optimal policy can require fewer prediction samples than estimating the Bayesian value function.

1 Introduction

Multi-step predictions may help decision makers adapt to future uncertainty, but directly adding them to the state can cause exponential growth and make planning intractable. The paper studies discounted finite MDPs under block feedback and develops a Bellman framework, value analysis, and learning results for this setting.

1.1.1 Low-Dimensional Bellman Representation

  • The optimal value has a Bellman representation on the original state space, even though the policy can use prediction information and adapt to states within each block.The Bayesian Bellman operator is a γ^K-contraction, and its unique fixed point equals the optimal block-feedback value.Source: §1.1.1 · p. 2

1.1.2 Value of Predictive Information

  • Observing predictions changes the local order of maximization and expectation; under exact full coverage, the gap to full information is O(γ^K/(1−γ)), while uniform error ε incurs O(ε/(1−γ)^2) loss.Matching lower bounds show these finite-horizon and prediction-error dependences cannot be improved in general.Source: §1.1.2 · pp. 2–3

1.1.3 Minimax-Optimal Policy Learning

  • BF–BOLA estimates uncovered transition rows from environment samples and the prediction distribution from independent prediction samples, with matching minimax bounds up to logarithmic factors.Prediction coverage reduces the environment-learning dimension to uncovered rows, and near-optimal policy learning can require fewer prediction samples than Bayesian value estimation.Source: §1.1.3 · p. 3

1.2.1 Model-Based RL

  • The model-based learning problem estimates uncovered transition rows from environment samples while using predictions for covered rows, reducing the environment-sample dimension.The environment-sample complexity scales with the number of uncovered rows.Source: §1.2.1 · p. 4

1.2.2 Decision Making with Lookahead Information

  • Unlike rolling-lookahead approaches, predictions here refresh only at block boundaries; within-block planning takes O(K|S|^2|A|) operations per observed prediction.The Bayesian value remains on the original state space.Source: §1.2.2 · pp. 4–5

1.2.3 Information in Stochastic Decision Problems

  • The paper quantifies transition-prediction value through its effect on the Bellman equation, especially the ordering of expectation and maximization..Source: §1.2.3 · p. 5

2 Model and Decision Protocols

The section specifies a discounted MDP with probabilistic transition predictions revealed at block boundaries, then compares block feedback with fixed- and receding-horizon planning. Block feedback keeps state feedback within each block while reusing the same prediction.

2.1 Preliminaries on Markov Decision Processes

  • The model is a discounted infinite-horizon MDP with finite state and action spaces, unknown transitions and rewards, and deterministic rewards normalized to [0, 1].Source: §2.1 · p. 5

2.2 Transition Predictions

  • At each block boundary, probabilistic predictions specify next-state distributions by phase for covered action rows; predictions are independent across blocks, average to the base kernel, and remain fixed within a block.Source: §2.2 · pp. 5–6

2.3 Decision Making under Block Feedback

  • Block feedback uses one prediction throughout each K-period block, while the decision maker observes the current state before every action and may adapt to realized states.Source: §2.3 · p. 6

2.4 Reference Decision Protocols

  • Fixed-horizon planning is worst-case NP-complete; block feedback uses a K-stage dynamic program with dense tabular cost O(K|S|2|A|), while receding-horizon storage scales as |S|B^K.Source: Table 1 · p. 7, §2.4 · p. 7
  • Fixed-horizon planning commits to an open-loop action sequence, whereas receding-horizon planning updates predictions each period and generally requires an augmented state.Source: §2.4 · p. 7

3 Prediction-Aware Bellman Theory

The paper avoids placing the current prediction in the infinite-horizon state by evaluating block feedback on the original state space. Its Bellman equation averages the optimized within-block value over predictions and yields an optimal policy that acts on each observed state.

3.1 Direct Augmented-State Formulation

  • The direct Markov representation includes state, prediction, and phase, and discretizing predictions can make the augmented state space grow exponentially with horizon.Source: §3.1 · pp. 7–8

3.2 Bayesian Block-Feedback Value

  • The Bayesian block-start value averages over predictions before observation, transitions, and policy randomization, while allowing the policy to use each prediction once observed.Source: §3.2 · p. 8

3.3 Block-Feedback Bellman Equation

  • The block-feedback Bellman operator optimizes within the block for each observed prediction, then averages over predictions; its unique fixed point is the optimal value and it is a γ^K-contraction.Source: §3.3 · p. 8
  • The Bayesian value has only |S| entries, and for each observed prediction the within-block optimization is a K-stage dynamic program.Source: §3.3 · p. 8

3.4 Optimal Block-Feedback Policies

  • An optimal block-feedback policy chooses a maximizing action at each phase for the realized state and prediction, using the Bayesian value at the next block boundary.Source: §3.4 · p. 9

4 The Value of Predictions

The section explains why transition predictions can raise value through recursive Bellman reordering and orders prediction regimes by information. It bounds horizon, prediction-error, and coverage losses and gives matching lower bounds for horizon and error dependence.

4.1 Bellman–Jensen Effect and Value Ordering

  • Exact one-step predictions let actions depend on observed transition information before selection, so E[max_a X_a] ≥ max_a E[X_a] yields a local gain that recurs through the Bellman expansion.The recursive reordering is the Bellman–Jensen effect.Source: §4.1 · p. 9
  • Theorem 4.1 orders values from no prediction through imperfect and exact predictions with partial or full coverage to a full-information oracle, with more information never reducing value.The comparison holds the transition process fixed; values coincide when there is only one action or a covered signal reveals no additional information.Source: §4.1 · pp. 9–10

4.2 Quantitative Value-of-Information Bounds

  • Theorem 4.2 separates full-information loss into horizon, prediction-error, and incomplete-coverage components, with coverage loss depending on whether uncovered rows can change the optimal action.Horizon loss is bounded by discounted rewards after the first K periods; error and coverage effects recur across blocks, amplified by (1 − γ^K)^−1.Source: §4.2 · pp. 10–11
  • For phase errors ε_j ≤ ε, the prediction-error bound is at most γ ε/(1 − γ)^2, so error does not accumulate linearly with prediction horizon.The one-block coverage gap is zero under full action coverage and otherwise depends on the value of revealing uncovered rows.Source: §4.2 · p. 11

4.3 Matching Lower Bounds

  • Theorem 4.3 gives a matching worst-case horizon-loss order γ^K/(1 − γ), with the hard instance delaying decisive branch information until after the current prediction horizon.Theorem 4.4 likewise matches the error dependence up to constants until the gap reaches the total discounted reward range, with value gain of order ε/(1 − γ)^2.Source: §4.3 · pp. 11–12

5 Sample-Efficient Learning under Block Feedback

BF–BOLA estimates a Bayesian value offline from uncovered-transition and prediction samples, then adapts online to each block's observed prediction. Its policy-learning guarantees are minimax-optimal up to logarithmic factors in stated regimes, and exploit prediction coverage and the distinction between policy learning and value estimation.

5.1 Sampling Model

  • The learner uses independent samples from uncovered transition rows and from the K-step prediction law; the latter samples contain prediction tables for covered rows.The environment-sample budget counts samples per uncovered row, while the prediction budget counts prediction draws.Source: §5.1 · p. 12

5.2 BF–BOLA: Offline Bellman Learning and Online Policy Adaptation

  • Offline, BF–BOLA computes an empirical Bayesian value; online, it combines that value with the fresh block prediction to adapt actions to realized states.The learned value remains a function on S, and a current online prediction need not have appeared in training samples.Source: §5.2 · p. 12, §5.2.2 · p. 13, §5.2.3 · pp. 13–14

5.2.1 Model Estimation

  • Covered actions use prediction rows observed in the current block, while uncovered actions use transition rows estimated from environment samples.The empirical prediction law estimates the block-boundary expectation used in the Bayesian Bellman operator.Source: §5.2.1 · p. 13

5.2.2 Offline Bayesian Value Estimation

  • The empirical block-feedback Bellman operator is a γ^K-contraction with a unique fixed point, which BF–BOLA computes offline by value iteration.Training predictions enter through the empirical average in the operator.Source: §5.2.2 · p. 13

5.2.3 Online Policy Adaptation

  • Each offline Bellman update costs O(N2 K|S|^2|A|) operations, while online adaptation to a fresh prediction costs O(K|S|^2|A|).The value function itself has only |S| coordinates.Source: §5.2.3 · p. 14

5.4 Minimax Lower Bounds and Policy–Value Separation

  • BF–BOLA learns near-optimal block-feedback policies with upper sample bounds matched by minimax lower bounds up to logarithmic factors in the stated accuracy regimes.The matching prediction-sample lower bound applies to model classes containing the O(K)-state hard family, for example when |S| ≥ C_0K.Source: §5.3.1 · p. 14, §5.4 · p. 16

5.3.1 Policy Learning Guarantees

  • The environment-sample requirement scales with |S|(|A| − |A−|), so predictions remove covered transition rows from the model-estimation burden.With full coverage, the transition-learning component disappears, leaving the additive |S||A| reward-observation cost.Source: §5.3.1 · pp. 14–15

5.4 Minimax Lower Bounds and Policy–Value Separation

  • Policy learning uses fewer prediction samples than Bayesian value estimation can require because the current prediction is used directly at deployment, whereas value estimation must also estimate its current-block average.The policy-learning contribution from future blocks is discounted by γ^K; the value-estimation rate is larger because it targets the prediction-averaged value before the current prediction is observed.Source: §5.4 · pp. 16–17

6 Numerical Experiments

The experiments examine prediction value, BF–BOLA learning, and a wind-storage control case study. They report value gains from prediction-aware feedback, learning behavior consistent with the sample-complexity analysis, and operating-cost savings in the calibrated case study.

6.1 Experimental Design

  • The experiments use a four-state, three-action production MDP with γ = 0.92 and a data-calibrated wind-storage MDP based on 52,404 timestamp-aligned observations.In the wind-storage setting, BF had no higher optimal cost than FH in any tested model or setting, and the prediction benefit vanished as η reached 1.Source: §6.1 · p. 17, §6.4 · pp. 18, 20

6.2 Value of Information

  • In the production MDP, block feedback and rolling-horizon policies both gained over one-step prediction, while noisier signals and reduced action coverage lowered value.The BF curve was not monotone in K because changing K also changed block boundaries; FH had negative gain at zero coverage due to open-loop commitment.Source: §6.2 · p. 17, Figure 1 · p. 18

6.3 Learning Efficiency

  • At D2 = 2048, policy success for ε_pol = 10^-3 was 95%, while mean Bayesian value error remained approximately 1.2 × 10^-2.Value errors decreased roughly as the inverse square root of sample size.Source: §6.3 · p. 18

6.4 Wind-Storage Control Case Study

  • At K = 3 and η = 0.15, mean paired savings over no prediction were 12.9% for BF and 16.2% for RH; one-step BF saved 8.6% across 12 fitted MDPs.Increasing K from 1 to 5 raised mean savings to 15.0% for BF and 18.0% for RH.Source: §6.4 · pp. 19–20, Figure 3 · p. 20

7 Conclusion

The conclusion presents block feedback as a low-dimensional Bellman framework for prediction-aware RL, with value analysis and a learning algorithm. The appendix supports this framework by establishing state-based fixed-point evaluation and comparing prediction regimes under a common coupling.

7 Conclusion

  • Prediction coverage reduces the environment-sampling dimension, and near-optimal policy learning can require fewer prediction samples than Bayesian value-function estimation.The conclusion also identifies richer receding-horizon protocols and low-dimensional representations for them as open directions.Source: §7 · pp. 20–21

Appendix Roadmap

  • The appendix roadmap assigns Bellman optimality and information ordering to Appendix A, value-of-information bounds to B, and learning bounds to C–E.Appendix F contains reference-protocol results.Source: Appendix Roadmap · p. 27

A.1 Proof of Theorem 3.1

  • The block-feedback Bellman operator is a γ^K-contraction with a unique fixed point that equals the optimal Bayesian value.The value carried across block boundaries depends on the state, not the previous block's prediction.Source: §A.1 · p. 27

A.2 Prediction Model and Coupling

  • Under the common coupling, exact full-coverage predictions reveal covered next states, while uncovered rows retain the base transition law.The proof removes the imperfect signal from the value recursion once the exact prediction is known, yielding equal values for the two regimes.Source: §A.2 · p. 28

A.3 Proof of Theorem 4.1

The proof compares prediction regimes and the full-information oracle, then bounds losses from finite horizon, partial action coverage, and prediction error. A separate comparison establishes that within-block feedback is at least as valuable as open-loop block planning.

A.3 Proof of Theorem 4.1

  • Exact predictions on all actions, exact predictions on a subset, and imperfect predictions on that subset are ordered by information; every block-feedback policy is admissible under offline information.The oracle value is the limit of finite-horizon values, with error at most γ^k/(1 − γ) after k periods.Source: §A.3 · p. 28

B.1 Proof of Theorem 4.2

  • The proof bounds ∥Vpart − Vimp∥∞ by A2; combining three comparisons yields an A1 + A2 + A3 bound, and the value gap is also at most (1 − γ)^−1.Rewards lie in [0, 1].Source: §B.1 · p. 29

B.2 Reference Comparison with Open-Loop Block Planning

  • Block feedback can mimic any open-loop action sequence and can only gain from adapting to within-block state feedback.The comparison uses the same prediction horizon, predictable action set, and prediction-error profile.Source: §B.2 · p. 30

B.3 Proof of Theorem B.1

The proof establishes the ordering between block-feedback and open-loop values by comparing their Bellman operators and fixed points. It also shows how a block-feedback rule can match an offline policy's state-action marginals over the current block.

B.3 Proof of Theorem B.1

  • Every open-loop block sequence is a state-independent block-feedback rule, so the block-feedback operator is no smaller and its value is at least the open-loop value.The proof compares fixed points of monotone γ^K-contractions.Source: §B.3 · p. 30

B.4 Current-Prediction Policy Matching

  • Conditioned on the current exact next-state table, a randomized block-feedback rule can match an offline policy's state-action marginals at every phase and its expected discounted reward over K periods.The rule selects actions according to the offline policy's conditional action distribution given the current state and block-start state.Source: §B.4 · pp. 30–31

B.5 Proof of Theorem 4.3

The construction isolates the finite prediction horizon as the source of a value gap: the initial prediction does not reveal the later branch outcomes, while the offline oracle sees both before choosing. The resulting lower bound grows with the discounted horizon scale.

B.5 Proof of Theorem 4.3

  • In this construction, block feedback and open-loop K-step prediction have the same value because no useful within-block choice remains after branch selection.Deviating from the advance action sends the process to the bad absorbing state.Source: §B.5 · p. 31
  • The current K-step prediction gives no information about which symmetric branch will reach the good state after the branch has been selected.The terminal random rows lie outside the initial horizon and are independent of the prediction rows at earlier phases.Source: §B.5 · p. 31
  • γ^K/[8(1 − γ)] is a lower bound on the value gap for γ ≥ 1/2, with exact predictions and full action coverage.The two branch outcomes are not revealed within the initial prediction horizon, but the offline oracle can choose after observing them.Source: §B.5 · pp. 31–32

B.6 Proof of Theorem 4.4

Theorem 4.4’s construction shows that exact predictions can create a value gap even when imperfect predictions are calibrated and share the same physical transition kernel. The BF–BOLA value-estimation proof separates uncovered-row transition error from prediction-law error.

B.6 Proof of Theorem 4.4

  • The exact and imperfect prediction laws use the same physical transition kernel, and the imperfect prediction is calibrated with uniform row error at most ε.The risky row’s natural error is 4q(1−q)≤ε at every phase.Source: §B.6 · p. 32
  • The value gap is at least cε/(1−γ)^2 when ε≤4(1−γ), and at least c/(1−γ) when ε>4(1−γ).The construction uses a risky action tied with a safe action under the imperfect prediction; exact predictions reveal success or failure and allow the action choice to adapt.Source: §B.6 · p. 32

C.1 Proof of Theorem 5.2

  • The Bayesian value-estimation proof replaces the empirical transition model first and the empirical prediction law second, bounding uncovered-row and prediction-law errors separately.The two data sources are independent, so applying the two bounds with failure probability δ/2 each gives both estimates with probability at least 1−δ.Source: §C.1 · p. 33, C BF–BOLA Bayesian Value Estimation · p. 33

C.2 Supporting Bounds for Theorem 5.2

This section develops variance-based perturbation bounds and stability-based concentration tools for transition and prediction-law estimation, including deterministic replace-one bounds. It uses these tools to establish BF–BOLA’s policy-learning guarantee and computational costs, with the proof handling the two regimes γK < 1/2 and γK ≥ 1/2 separately.

C.2 Supporting Bounds for Theorem 5.2

  • For a Markov reward process, the return-variance recursion W = q + β²MW and a discounted variance bound support comparisons between prediction-dependent and full Bellman-target variances.The same variance-bound argument extends to general-state-space Markov kernels.Source: §C.2 · pp. 33–34

C.2.1 Proof of Lemma C.2

  • The transition-perturbation proof uses an augmented MDP and variance transfer to bound accumulated second moments S and residuals R, under λ ≤ c/H².The displayed bounds are S ≤ CH² + CHE² and R ≤ CH^(3/2) + CHE.Source: §C.2.1 · p. 35

C.2.2 Proof of Lemma C.3

  • The prediction-law perturbation proof concentrates fixed true-value targets, transfers variance to sample-dependent targets, and handles both upper and lower value deviations to establish Lemma C.3’s bound.The proof’s concluding step uses the sample-size condition λ ≤ c h².Source: §C.2.2 · pp. 36–37

C.3 Proof of Proposition 5.1

  • Each sweep costs O(N₂K|S|²|A|) arithmetic operations, while processing one new online prediction costs O(K|S|²|A|).The empirical operator’s γK-contraction determines the number of sweeps needed for a target accuracy.Source: §C.3 · p. 37

D BF–BOLA Policy Learning

  • The BF–BOLA learning proof combines current-block cancellation with stability, concentration, and variance bounds to control remaining errors.Source: D BF–BOLA Policy Learning · p. 37

D.1 Proof of Theorem 5.1

  • The proof defines transition and prediction sample budgets as D₁ = |U|N₁ + |S||A| and D₂ = N₂; the transition contribution vanishes when U is empty.The budgets include one reward observation per state-action pair.Source: §D.1 · p. 38

D.1.1 Current-Block Cancellation

  • Comparing action choices under the same observed prediction cancels current-block prediction error, so prediction-law error contributes only through future blocks.The cancellation follows because changing current-prediction probabilities does not change the greedy rule computed separately for each prediction.Source: §D.1.1 · pp. 38–39

D.1.2 Completing the Policy Bound

  • In both cases, the proof bounds ∥(V−W)+∥∞≤Cεpol; comparing V with V* yields ∥V*−W∥∞≤Cεpol, and it also obtains Eπ≤Cεpol.Source: §D.1.2 · pp. 39–40
  • The two policy-bound cases hold on one joint event, and the prescribed accuracy follows after increasing the universal sample-size constant and counting D1 and D2 samples.The counts are D1 = |S|(|A| − |A−|)N1 + |S||A| and D2 = N2.Source: §D.1.2 · p. 40

D.2.1 Policy-Evaluation Identities

  • The policy comparison sharpens the evaluation-error bound by cancelling the current-block prediction residual, and both identities hold for every training dataset.Equation (38) converts residual bounds into an evaluation-error bound; Lemma D.1 gives the sharper policy comparison.Source: §D.2.1 · p. 40

D.2.2 Stability-Based Bernstein Perturbation

  • Because empirical Bellman targets depend on their training samples, stability-based concentration replaces a fixed-target Bernstein argument and retains dependence on target variance.The scalar stable-Bernstein lemma also permits conditioning on independent external randomness when its stability bound holds after conditioning.Source: §D.2.2 · pp. 40–41
  • Measurable tail-level scores let residual concentration bounds be averaged over predictions, including continuous prediction spaces, without discretization.The averaged-prediction lemma constructs nonnegative measurable scores that hold pointwise across the finite index set and prediction space.Source: §D.2.2 · p. 42
  • Replacing one uncovered transition sample changes the fixed point by at most C H^2/N1, while replacing one prediction changes it by at most C H/[N2(1 − γ^K)].The corresponding next-state target bounds are given in the transition and prediction replace-one results.Source: §D.2.2 · p. 43

D.2.3 Transition-Error Propagation

The proof propagates uncovered-row transition error through the learned policy while separating local residuals from terminal-value error. It then develops fixed-law perturbation and variance bounds used to combine residual estimates in the short-block regime and prove lower bounds.

D.2.3 Transition-Error Propagation

  • The accumulated transition error has a leading term of order H^3/2/√N1 on uncovered rows, alongside a discounted terminal-value error.The proof bounds local errors using the score budget and variance bound, then combines them with the terminal contribution.Source: §D.2.3 · pp. 44–45

D.2.4 Transition Perturbation under a Fixed Prediction Law

  • Under a fixed prediction law independent of transition samples, the proof compares optimal values by evaluating each model’s optimal rule under the other model.The law may have arbitrary support; the transition perturbation argument applies to both empirical-greedy and sample-independent fixed rules.Source: §D.2.4 · pp. 45–46

D.2.5 Prediction Terms After Cancellation

  • After cancellation, the prediction terms comprise terminal-value error and prediction residual; the latter requires a stability bound because its target depends on the learned value.The terminal-value target is independent of prediction samples and is handled with Bernstein’s inequality and the block-operator contraction.Source: §D.2.5 · pp. 46–47

D.2.6 Block-Level Variance Bounds

  • Conditioning on training data turns the learned BF rule into a block-boundary Markov reward process with returns in [0,H], yielding a bound on true-target variance.The empirical-target variance is then related to the true-target variance through their within-block value comparison.Source: §D.2.6 · p. 47

Combining the two variance-transfer bounds gives

D.2.7 Short-Block Regime: Combining the Residual Bounds

  • In the short-block regime γ^K≥1/2, the proof uses the same prediction-sample order as Bayesian value estimation and obtains policy evaluation error at most Cε_pol.The sample-size conditions absorb the learned-policy error term, while stability permits data-dependent targets and maximum row-phase scores accommodate row choice.Source: §D.2.7 · p. 48

E Lower Bounds for Learning

  • The lower-bound proofs construct two nearby models requiring different accurate learner answers, then use the learner’s answer to distinguish them.To isolate one sample type, the other type’s observation distribution is made identical under both models.Source: E Lower Bounds for Learning · p. 49, §E.1 · p. 49

E.1 Testing Reduction and Main Proofs

  • A test with error at most 1/3 under each model requires total variation at least 1/3 and KL divergence at least 2/9.Source: §E.1 · p. 49

E.1.1 Proof of Theorem 5.3

The lower-bound proofs reduce learning to hard instances in uncovered transition rows or prediction laws that differ only in how often they reveal outcomes. Additional constructions preserve these bounds for value estimation and distinguish block-feedback planning from reference protocols with different computational costs.

E.1.1 Proof of Theorem 5.3

  • Ω(|S|m/((1 − γ)^3 ε_pol^2)) environment samples are necessary when m ≥ 2 uncovered actions contain a classical discounted-MDP hard family.Covered actions are made known and dominated.Source: §E.1.1 · p. 49
  • For m = 1, the policy-learning lower bound is D1 ≥ c n/((1 − γ)^3 ε_pol^2), with n = Θ(|S|).The construction requires samples from every gadget.Source: §E.1.1 · p. 49

E.1.2 Proof of Theorem 5.4

  • Theorem 5.4’s value-estimation lower bound embeds a classical hard MDP in uncovered rows while preserving its optimal value and sampling information.Prediction samples distinguish the prediction laws when transition probabilities and rewards are identical.Source: §E.1.2 · pp. 50–51, §E.4 · p. 53

E.2 Supporting Constructions for Theorem 5.3

  • The policy-separation construction places a known reference value between two possible risky-state values, forcing different branches across models.For the single-uncovered-action gadget, the action gap is at least 8ε_pol.Source: §E.2 · p. 51

E.3 Prediction-Sample Parameter Checks for Theorem 5.4

  • For value estimation, removing the predecessor decision state avoids an extra block discount, and the chosen prediction-law parameters yield a value gap greater than 2ε_est.The KL estimate is checked across both block-discount regimes.Source: §E.3 · pp. 52–53

E.4 Classical Embedding for Theorem 5.4

  • Theorem 5.4’s classical embedding makes covered actions known zero-reward transitions, so prediction queries reveal no additional information about the hard family.The construction preserves the optimal value and leaves the classical lower bound applicable.Source: §E.4 · p. 53

F.1.2 Receding Horizon as an Augmented MDP

  • Receding-horizon planning is exactly an augmented MDP on S × Q_K, whose tabular representation can grow exponentially with K.Its exact tabular representation has at least Ω(|S||Q_K|) entries.Source: §F.1.2 · p. 54

F.1.3 Exact-Tabular Complexity of the Reference Protocols

  • Fixed-horizon open-loop planning is NP-complete even with binary actions and deterministic predictions; receding-horizon dense Bellman sweeps cost O(|S|^2|A|B^(2K)).The fixed-horizon hardness follows from a reduction from 3-SAT.Source: §F.1.3 · pp. 54–55

F.2 Proof of Theorem F.1

The fixed-horizon Bayesian Bellman operator averages optimized open-loop block values over predictions. Its contraction property yields the optimal Bayesian value as its unique fixed point.

F.2 Proof of Theorem F.1

  • The fixed-horizon operator averages the open-loop block value over the prediction distribution.Source: §F.2 · p. 55
  • Changing the terminal value changes each block return by at most γ^K times the sup-norm difference, so the operator is a monotone γ^K-contraction.Source: §F.2 · p. 55
  • The policy-evaluation and greedy-policy argument identifies the operator’s unique fixed point with the optimal fixed-horizon Bayesian value.Source: §F.2 · p. 55
Loading 2610.32887v1…