PaperlayerView exact revision on arXiv

Source-linked AI summary

Settling the Sample Complexity of Model-Based Offline Reinforcement Learning

Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, Yuting Wei

arXiv:2204.05275v4stat.MLcs.ITcs.LGcs.SYeess.SYmath.ITmath.STstat.TH

TL;DR

Offline RL must learn from historical data when online collection is costly and behavior-policy data differs from the target policy. The paper studies pessimistic model-based value iteration with Bernstein-style penalties and establishes minimax-optimal sample complexity across the full accuracy range without burn-in for tabular MDPs.

  • Problem

    Offline RL must use historical data when online collection is costly, despite distribution shift between behavior-policy data and the target policy.

    Source: §1 · p. 2, §1.1 · p. 3

  • Method

    The paper uses pessimistic value iteration with Bernstein-style penalties to account for uncertainty in the empirical MDP.

    Source: §2.2 · p. 10, §6.2 · p. 26

  • Results

    The model-based approach is near-minimax optimal for finite- and infinite-horizon tabular MDPs across the entire accuracy range, with no burn-in cost.

    Source: §1.3 · p. 6, §8 · p. 38

  • Takeaways & Limitations

    Reliable transition-kernel estimation may be infeasible in the sample-starved regime, yet the plug-in approach can still learn the optimal policy.

    Source: §8 · p. 38

    The sample-size improvement depends on model compressibility implied by a small C⋆.

    Source: §3.4 · p. 20

Abstract

from arXiv · show

This paper is concerned with offline reinforcement learning (RL), which learns using pre-collected data without further exploration. Effective offline RL would be able to accommodate distribution shift and limited data coverage. However, prior algorithms or analyses either suffer from suboptimal sample complexities or incur high burn-in cost to reach sample optimality, thus posing an impediment to efficient offline RL in sample-starved applications. We demonstrate that the model-based (or "plug-in") approach achieves minimax-optimal sample complexity without burn-in cost for tabular Markov decision processes (MDPs). Concretely, consider a finite-horizon (resp. $\gamma$-discounted infinite-horizon) MDP with $S$ states and horizon $H$ (resp. effective horizon $\frac{1}{1-\gamma}$), and suppose the distribution shift of data is reflected by some single-policy clipped concentrability coefficient $C^{\star}_{\text{clipped}}$. We prove that model-based offline RL yields $\varepsilon$-accuracy with a sample complexity of \[ \begin{cases} \frac{H^{4}SC_{\text{clipped}}^{\star}}{\varepsilon^{2}} & (\text{finite-horizon MDPs}) \frac{SC_{\text{clipped}}^{\star}}{(1-\gamma)^{3}\varepsilon^{2}} & (\text{infinite-horizon MDPs}) \end{cases} \] up to log factor, which is minimax optimal for the entire $\varepsilon$-range. The proposed algorithms are "pessimistic" variants of value iteration with Bernstein-style penalties, and do not require sophisticated variance reduction. Our analysis framework is established upon delicate leave-one-out decoupling arguments in conjunction with careful self-bounding techniques tailored to MDPs.

1 Introduction

Offline RL uses previously collected data, but must contend with distribution shift and limited coverage. This section motivates and studies whether model-based offline RL can achieve minimax-optimal sample complexity without burn-in, using pessimistic value iteration.

1.1 Challenges: distribution shift and limited data coverage

  • Offline RL uses historical data without further exploration, while distribution shift and limited data coverage challenge its statistical efficiency.Data may come from a behavior policy different from the optimal policy, and uniform state-action coverage can be unrealistic or unnecessary when seeking one optimal policy.Source: §1 · p. 2, §1.1 · p. 3

1.2 Inadequacy of prior works

  • Earlier guarantees were either sample-suboptimal or required substantial burn-in to attain optimality, motivating simpler, sample-efficient offline RL methods.The paper studies pessimistic value iteration with Bernstein-style penalties for discounted infinite-horizon and finite-horizon MDPs.Source: §1.2 · pp. 4–5, §1.3 · p. 5

1.3 Main contributions

  • The paper studies whether model-based offline RL can achieve near-optimal sample complexity without burn-in or sophisticated variance reduction, and answers affirmatively.Its analysis establishes minimax-matching lower bounds and upper bounds for the full target-accuracy range.Source: §1.2 · p. 5, §1.3 · pp. 5–6
  • VI-LCB with Bernstein-style penalties is presented for discounted infinite-horizon and finite-horizon MDPs, with minimax-optimal guarantees across the target-accuracy range.The finite-horizon variant uses two-fold subsampling; the paper also reports that sophisticated variance reduction is unnecessary.Source: §1.3 · pp. 5–6
  • The paper introduces a single-policy clipped concentrability coefficient, a modified distribution-mismatch measure that slightly improves the resulting sample-complexity bound.The notation section also defines conventions for vectors, matrices, and asymptotic order notation.Source: §1.3 · p. 5, §1.4 · p. 6

2 Algorithm and theory: discounted infinite-horizon MDPs

This section presents VI-LCB for discounted infinite-horizon offline RL and establishes high-probability ε-accuracy with minimax-optimal sample complexity up to logarithmic factors across the full accuracy range, without burn-in. It characterizes data mismatch via single-policy clipped concentrability and analyzes benefits of sample reuse and low clipped concentrability using leave-one-out and self-bounding techniques.

2.1 Models and assumptions

  • The setting uses independent transitions from a behavior state-action distribution and known rewards, while single-policy concentrability measures mismatch against the optimal policy’s occupancy.Unlike an all-policy density-ratio bound, the single-policy condition concerns only π⋆; the clipped version can allow low data coverage for rarely optimal state-action pairs.Source: §2.1 · pp. 8–9
  • Very small C⋆ clipped requires highly compressible optimal occupancy, a regime the authors caution may not describe real-world data.The clipped coefficient’s lower bound is nearly tight and can yield sample savings in some cases.Source: §2.1 · p. 9

2.2 Algorithm: VI-LCB for infinite-horizon MDPs

  • VI-LCB applies value iteration to the empirical MDP with a Bernstein-style variance penalty, reusing samples across iterations rather than sample-splitting as in Rashidinejad et al. (2022).The Bernstein penalty exploits variance structure across time, unlike the Hoeffding-style penalty in Rashidinejad et al. (2022); pessimism suppresses unreliable, poorly visited actions.Source: §2.2 · pp. 10–12
  • The penalized Bellman operator remains a γ-contraction with a unique fixed point, so VI-LCB’s iterates converge linearly to that fixed point.This preserves the contraction property despite incorporating penalties.Source: §2.2 · p. 11

2.3 Performance guarantees

  • VI-LCB achieves ε-accuracy with high probability and is sample-optimal across the full ε-range, with guarantees stated using C⋆ clipped or C⋆.The guarantee holds with sufficiently large penalty constant and enough iterations; the paper also notes that the required sample count can be below the transition-kernel dimension, even when model estimation is unreliable.Source: §2 · p. 7, §2.3 · p. 12
  • The model-based plug-in approach can enable reliable offline learning even when estimating the transition model reliably is impossible.The theorem’s sample requirement can be far smaller than the transition kernel’s ambient dimension S^2A.Source: §2.3 · p. 12
  • The Bernstein-penalized algorithm’s sample complexity matches the minimax lower bound up to logarithmic factors, improving the effective-horizon dependence over Rashidinejad et al. (2022).The lower-bound result also covers cases where the clipped concentrability coefficient is much smaller than the ordinary coefficient.Source: §2.3 · p. 13
  • The sample-size bound holds across the full ε-range, eliminating the burn-in cost required by the prior sample-optimal result of Rashidinejad et al. (2022).The prior result required burn-in of at least order S C⋆/(1−γ)^5.Source: §2.3 · p. 13
  • Unlike prior analyses that split data across iterations, the algorithm reuses all samples at every iteration, improving information use in sample-starved settings.The paper identifies sample reuse as a factor in its sample-complexity improvement over Rashidinejad et al. (2022).Source: §2.3 · p. 13
  • When clipped concentrability is O(1/S), sample requirements can be much lower because the condition implies compressible structure concentrated on a few important states.The lower-bound construction indicates that the target distribution may assign exceedingly small probability to remaining states, allowing attention to focus on important states.Source: §2.3 · p. 13
  • The analysis combines leave-one-out decoupling across iterations with self-bounding control of quantities such as empirical variance, supporting optimality in the most sample-starved regime.The paper attributes gains over Rashidinejad et al. (2022) to sample reuse and Bernstein-style penalties, and contrasts its result with prior discounted-RL methods that were suboptimal or required large burn-in.Source: §2.3 · p. 14

3 Algorithm and theory: episodic finite-horizon MDPs

This section develops and analyzes pessimistic model-based value iteration for finite-horizon offline RL, using two-fold subsampling to address dependence among trajectory transitions. It establishes high-probability guarantees, including sample optimality up to logarithmic factors across the full accuracy range without burn-in, and guarantees for unreliable model estimation and instance-dependent settings.

3.1 Models and assumptions

  • The goal is a near-optimal policy for a test initial-state distribution from i.i.d. behavior-policy trajectories, with distribution shift measured by single-policy clipped concentrability and accuracy targeted across epsilon in (0,H].The learner is also assumed to have access to the reward function.Source: §3.1 · pp. 15–16

3.2 A model-based offline RL algorithm: VI-LCB

  • VI-LCB runs backward value iteration on an empirical transition model, subtracting Bernstein-style lower-confidence penalties and choosing actions greedily from the resulting Q estimates.Its variance term uses the empirical transition kernel because the true kernel is unavailable.Source: §3.2 · pp. 16–17

3.3 VI-LCB with two-fold subsampling

  • Two-fold subsampling addresses temporal dependence by splitting trajectories, estimating lower bounds on state-step counts from one half, and subsampling transitions from the other; it avoids prior H-fold splitting.The auxiliary count estimates are independent of the retained transitions, which can almost be treated as statistically independent.Source: §3.3 · pp. 17–18

3.4 Performance guarantees

  • For ε∈(0,H] and 0<δ<1, Algorithm 3’s returned policy obeys the theorem’s guarantee with probability exceeding 1−12δ when penalties use Bernstein-style quantity (55) and trajectories are sufficiently numerous.The result also holds when C⋆ clipped is replaced with C⋆.Source: §3.4 · p. 19
  • The method can learn reliably even when its transition-model estimate is completely off, using subsampling-based decoupling and careful control of Bernstein-penalty variance.The total sample size may be far smaller than the transition kernel’s ambient dimension, S²AH.Source: §3.4 · p. 19
  • Theorem 3’s sample complexity is optimal up to logarithmic factors, as supported by the accompanying minimax lower bound.The lower bound applies to a collection of finite-horizon MDPs and shows that no estimator can uniformly avoid the stated sample requirement.Source: §3.4 · p. 19
  • The sample bound holds for every ε in (0, H], so the algorithm needs no burn-in to work sample-optimally.The passage contrasts this with prior model-based and model-free offline algorithms, which require significant burn-in sample sizes.Source: §3.4 · p. 19
  • When the clipped concentrability coefficient is small, sample complexity can fall through model compressibility, though this saving depends on that compressibility.The passages note that C⋆_clipped may be below 1 and that the resulting savings are not free of structural conditions.Source: §3.4 · p. 20
  • The algorithm needs no prior knowledge of C⋆_clipped, but the dataset may not reveal how many samples suffice, an information-theoretic limitation.The hard example shows that the data can fail to visit an action whose unknown parameter affects the clipped coefficient.Source: §3.4 · p. 20
  • For episodic finite-horizon MDPs, Algorithm 3’s dominant instance-dependent bound term matches the lower bound of Yin and Wang (2021, Theorem 4.3) for sufficiently large samples.This establishes instance optimality in that regime.Source: §3.4 · p. 20
  • Unlike prior variance-reduction approaches that require burn-in for optimality, this analysis shows variance reduction is unnecessary and yields a simpler algorithm and tighter analysis.The passage contrasts with Xie et al. (2021) and cites burn-in requirements in earlier work including Li et al. (2021), Sidford et al. (2018), Zhang et al. (2020), and Azar et al. (2017).Source: §3.4 · p. 21

4 Numerical experiments

The experiments evaluate VI-LCB on a finite-horizon gambler’s problem and compare it with value iteration without pessimism. VI-LCB performs better across the reported sample regimes, and its measured scaling agrees with the stated theoretical rate.

Gambler’s problem

  • The experiment models gambling as a finite-horizon MDP with balances 0–50, ending at 0, 50, or horizon H.The agent chooses an integer bet based on its balance; the stated setup uses H = 100 and a uniform initial-balance distribution.Source: §4 · p. 21
  • The historical offline dataset uses N independent samples drawn randomly for each state-action pair and time step.The coin’s probability of heads is fixed at 0.45 throughout the episode.Source: §4 · p. 21

Evaluation results

  • With N = 50, VI-LCB outperforms value iteration uniformly over the state space in the reported performance-gap evaluation.The comparison averages 10 independent experiments.Source: §4 · pp. 21–22
  • A log-log fit gives VI-LCB’s performance-gap scaling a slope of −0.502, matching Theorem 3’s stated N^-1/2 rate.The paper reports that VI-LCB consistently outperforms value iteration across the tested sample sizes, especially in the sample-starved regime.Source: §4 · p. 22

5 Related works

The related-work discussion distinguishes offline policy learning from off-policy evaluation and situates VI-LCB among pessimistic model-based methods. It contrasts this approach with online optimism and model-free methods that may require stronger coverage or burn-in costs.

Off-policy evaluation and offline RL

  • Offline policy learning seeks a near-optimal or improved policy, whereas off-policy evaluation estimates the value of a target policy differing from the behavior policy.The paper places its own work in the offline policy-learning category.Source: §5 · p. 22

Offline RL with the pessimism principle

  • Pessimistic offline RL uses lower confidence bounds to avoid overly uncertain regions, while Yin and Wang (2021) require a large burn-in sample size for minimax optimality across the full ε-range.The cited work’s burn-in requirement can be large when d_b min is exceedingly small.Source: §5 · p. 22

Online RL and the optimism principle

  • Online RL commonly uses optimism to select exploratory policies; Bernstein-style value bounds support sample-efficient exploration in model-based and model-free algorithms.The passage notes that Bernstein-style uncertainty estimation alone does not ensure regret optimality for model-free algorithms, motivating variance reduction.Source: §5 · pp. 22–23

Model-based RL; Model-free RL

  • Model-based RL separates model estimation from planning, while asynchronous Q-learning results cited here require stronger uniform coverage than the single-policy concentrability considered in this paper.The discussion also notes that variance-reduced model-free RL typically has a large burn-in cost to operate sample-optimally.Source: §5 · p. 23

6 Analysis: discounted infinite-horizon MDPs

This section establishes the discounted infinite-horizon guarantee by proving properties of the pessimistic value-iteration output and controlling its error through concentration and clipped concentrability. Its proof uses leave-one-out decoupling to address dependence between the empirical transition model and value estimates.

6 Analysis: discounted infinite-horizon MDPs

  • Theorem 5 supplies a high-probability guarantee for the discounted infinite-horizon setting, and the section derives ε-accuracy when the sample size exceeds its stated threshold.The supplied text does not include the threshold expression.Source: §6 · pp. 23–24

6.1 Preliminary facts

  • The preliminary facts bound the total transition counts N(s, a) with high probability, supporting later control of empirical-model errors and penalties.The count bound is stated simultaneously over all state-action pairs.Source: §6.1 · p. 24

6.2 Proof of Theorem 5

  • Leave-one-out decoupling addresses the dependence between the empirical transition model and reused value estimates, enabling Bernstein-style concentration bounds.Auxiliary MDPs omit samples from a given state and include one whose value function is close to that of the true MDP.Source: §6.2 · pp. 25–26

6.2 Proof of Theorem 5; Step 4: using concentrability to control

7 Analysis: episodic finite-horizon MDPs

The finite-horizon analysis establishes a high-probability theorem through bounded value iterates, an independence construction for the data, and concentration arguments. It uses these components to relate the pessimistic estimates to the returned policy and control their errors.

7.1 Preliminary facts and notation; Notation.

  • The iterates of Algorithm 2 are bounded between 0 and H − h + 1 at step h.The section also defines transition vectors and associated variance parameters for the true and empirical kernels.Source: §7.1 · pp. 31–32, Notation · p. 32

7.2 A crucial statistical independence property

  • The augmented trimmed dataset has the same distribution as an independent-sample dataset and equals the original trimmed dataset with probability exceeding 1 − 8δ.The construction is used to obtain the statistical independence property needed for the analysis.Source: §7.2 · p. 32

7.3 Proof of Theorem 3

  • Under conditional independence of sample transitions given {N_h(s,a)}, Theorem 6 provides a high-probability bound with probability at least 1−4δ when penalties are (55) and c_b≥16 is a constant.The proof invokes Theorem 6 on Dtrim, taking N_h(s,a)=N_trim.Source: §7.3 · p. 33

7.3.1 Proof of Theorem 6

  • A concentration lemma applies to vectors independent of the empirical transition model, with bounded norm and probability at least 1 − 4δ/H.The analysis uses the backward iteration so the next-step value estimate is independent of the current-step empirical kernel.Source: §7.3.1 · p. 33
  • The induction establishes that the pessimistic action-value estimates do not exceed the corresponding values of the returned policy.This lower-bound relation is used in the finite-horizon proof.Source: §7.3.1 · p. 34

8 Discussion

The paper establishes near-minimax sample complexity for model-based offline RL in tabular finite- and infinite-horizon MDPs, with no burn-in cost. It identifies extensions to other settings and sharper analysis as future directions.

8 Discussion

  • The tabular plug-in approach is near-minimax optimal for both finite- and infinite-horizon MDPs across the entire target-accuracy range, without burn-in cost.The paper attributes this result to Bernstein-style lower confidence bounds that capture variance at each iteration, without requiring sophisticated variance reduction.Source: §8 · p. 38
  • Avoiding Algorithm 3's two-fold subsampling may improve pre-constants and algorithmic simplicity, but cannot improve sample complexity in an order-wise sense.The authors identify sharp analysis of VI-LCB without sample splitting as an open problem because of dependencies across time steps.Source: §8 · p. 38
  • Whether sample-optimal model-free offline algorithms can have minimal burn-in periods remains open.The authors note the memory efficiency of model-free algorithms as motivation for this direction.Source: §8 · p. 38
  • Extending the analysis beyond tabular MDPs, including to low-complexity linear representations and multi-agent offline RL, remains future work.Source: §8 · p. 38

A.1 Proof of Lemma 1

The proof studies a pessimistic Bellman operator, establishing its monotonicity and contraction before using those properties to show that it has a unique fixed point.

A.1 Proof of Lemma 1

  • The proof defines a pessimistic Bellman operator that combines rewards, a penalty depending on the value vector, and discounted empirical next-state values.Source: §A.1 · pp. 38–39
  • Monotonicity of the operator is the key step used to establish its contraction property.The proof uses the invariance of the penalty to constant shifts in the value vector as part of this argument.Source: §A.1 · p. 39
  • The operator has a unique fixed point: the proof establishes convergence to a fixed point and uses contraction to rule out another one.Source: §A.1 · p. 41

A.2 Proof of Lemma 2

These proof sections establish a recursive bound for Lemma 2 and use Bernstein concentration with a union bound to control large-count state-action pairs in Lemma 4.

A.2 Proof of Lemma 2

  • The Lemma 2 proof recursively applies the operator properties to derive its bound, using the bounded fixed-point value in the final step.Source: §A.2 · p. 41

A.3 Proof of Lemma 4

  • For Lemma 4, Bernstein concentration and a union bound establish the claimed control simultaneously over the large-count state-action pairs.Source: §A.3 · p. 42

A.4 Proof of Lemma 5

The Lemma 5 proof decouples empirical transition estimates using auxiliary state-absorbing MDPs, then applies Bernstein bounds and a covering argument. The Lemma 9 proof relates true and empirical variance to obtain the needed concentration bounds.

A.4.1 Proof of Lemma 9

  • Lemma 9 provides Bernstein bounds for transition-estimation error and connects true variance to its empirical estimate.Source: §A.4 · p. 43, §A.4.1 · p. 47

A.4 Proof of Lemma 5

  • The leave-one-out argument uses these auxiliary MDPs to obtain value vectors independent of the transition estimate being bounded.The proof then uses an epsilon-net and a covering argument to extend the bounds across value vectors.Source: §A.4 · pp. 42–44
  • For each state and scalar u, the proof constructs an auxiliary MDP identical to the empirical MDP except at that state, which is made absorbing.Source: §A.4 · p. 43

A.4.1 Proof of Lemma 9

  • The Lemma 9 proof separates low- and high-variance cases to establish the advertised bound.Source: §A.4.1 · pp. 47–48

B.1 Proof of Lemma 3

This section develops concentration arguments for Lemma 3 and the instance-dependent bound, and outlines the hard-MDP construction and testing approach for Theorem 2’s minimax lower bound. It also argues that a condition required of the estimator in (205) cannot hold under sample-size condition (209), because that would contradict lower bound (210).

B.1 Proof of Lemma 3

  • Bernstein bounds and case splits establish the high-probability count claims (57a) and (57b) across states, actions, and horizons.The proof first establishes (57a), then uses it to support the simultaneous bound needed for (57b).Source: §B.1 · pp. 50–51

B.2 Proof of the instance-dependent statistical bound (65)

  • Relation (65) is derived using variance bounds, Cauchy-Schwarz, the clipped concentrability coefficient, and Theorem 6.The proof invokes relation (171) and Theorem 6’s result (116).Source: §B.2 · pp. 51–52

C.1 Preliminary facts

  • The preliminary facts define Bernoulli KL and chi-square divergences and establish KL inequalities, including a relation attributed to Tsybakov (2009).The proof of the first inequality reparameterizes the Bernoulli means and uses monotonicity in the resulting parameter.Source: §C.1 · pp. 52–53

C.2.1 Construction of hard problem instances

  • The hard-instance construction uses two MDPs parameterized by θ ∈ {0, 1}, each with S states and two actions.The construction also specifies value functions and optimal-policy properties for these MDPs.Source: §C.2.1 · pp. 53–54
  • The batch dataset uses i.i.d. samples, an initial-state distribution μ, and a uniform behavior policy; its occupancy state distribution is μ, and the test distribution characterizes C⋆_clipped.The construction selects the test distribution to relate the dataset’s single-policy clipped concentrability coefficient to the hard MDP.Source: §C.2.1 · p. 54

B.1 Proof of Lemma 3

  • The estimator defined in (205) must satisfy a derived condition, which cannot hold under (209) without contradicting lower bound (210).The supplied passages do not specify the derived condition.Source: §C.2.2 · p. 56

C.2.3 Proof of Lemma 11

The proof relates policy choices to value through a transition-probability quantity, establishes invariance of the state distribution under the behavior policy, and begins the hard-instance analysis for Theorem 4.

C.2.3 Proof of Lemma 11

  • x_{π,θ} = q + (p − q)π(θ | 0) expresses the transition probability as a function of the policy’s action probability in state 0.The proof uses that this quantity increases with π(θ | 0) when p ≥ q.Source: §C.2.3 · pp. 56–57

C.2.4 Proof of auxiliary properties

  • Starting from ρ_b = μ, the proof shows that s_t remains distributed as μ at every time under the behavior policy.It first derives s_1 ∼ μ, then repeats the argument for later steps.Source: §C.2.4 · pp. 57–58

C.3 Proof of Theorem 4

  • Theorem 4’s proof proceeds by constructing hard MDP and batch-data instances, then analyzing their sample complexity.The passage describes this as the proof’s two-part plan.Source: §C.3 · p. 59

C.3.1 Construction of hard problem instances

The lower-bound proof constructs separated MDP instances and uses multiple-hypothesis testing to show that an estimator cannot meet the target under the stated sample-size condition.

C.3.1 Construction of hard problem instances

  • The hard-instance family uses an exponentially large set Θ of sufficiently separated binary vectors, constructed using the Gilbert–Varshamov lemma.The separation property is identified as important to the ensuing analysis.Source: §C.3.1 · p. 60
  • The batch dataset consists of K independent sample trajectories, each of length H.The construction also specifies an initial-state distribution and behavior policy.Source: §C.3.1 · p. 61

C.3.2 Establishing the minimax lower bound

  • The lower-bound analysis frames recovery of θ as a |Θ|-ary hypothesis test and invokes Fano’s inequality and KL-divergence arguments.The passage also uses the shared occupancy state distribution across MDPs in the family.Source: §C.3.2 · p. 62
  • The proof concludes that the estimator’s required success cannot hold under the sample-size condition, yielding the minimax lower-bound argument.The conclusion follows by contradiction with the earlier testing result; the supplied passages do not state the condition’s explicit sample threshold.Source: §C.3.2 · p. 64

C.3.3 Proof of Lemma 12

The proof characterizes optimal choices in state 0 and bounds policy values, then establishes occupancy properties for the constructed instances.

C.3.3 Proof of Lemma 12

  • For any policy, the value function is bounded above by H − h + 1 at every state and step.The proof states this bound while deriving facts about the value at state 1.Source: §C.3.3 · p. 64

C.3.4 Proof of auxiliary properties

  • The behavior-policy state-action occupancy at step h is μ(s)/2, and the state occupancy at step 2 is μ.The proof says the state-occupancy argument can be repeated recursively across later steps.Source: §C.3.4 · p. 66

C.3.3 Proof of Lemma 12

  • For the constructed MDP, the optimal policy chooses action θ_h in state 0 at every step h.The auxiliary-property proof explicitly invokes this optimal-policy property.Source: §C.3.4 · p. 66

Related papers

Loading 2204.05275v4…