PaperlayerView exact revision on arXiv

Source-linked AI summary

Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model

Gen Li, Yuting Wei, Yuejie Chi, Yuxin Chen

arXiv:2005.12900v8cs.LGcs.ITmath.OCmath.STstat.ML

TL;DR

The paper addresses sample-efficiency barriers in model-based reinforcement learning with a generative model, where prior guarantees did not cover the full trade-off between sample complexity and statistical accuracy. It proposes model-based algorithms for discounted infinite-horizon MDPs and analyzes plain model-based planning for time-inhomogeneous finite-horizon MDPs, obtaining minimax-optimal guarantees across the relevant sample-size and accuracy ranges.

  • Problem

    Prior model-based reinforcement-learning guarantees for generative-model MDPs faced sample-size barriers, leaving the complete trade-off between sample complexity and statistical accuracy unresolved.

  • Method

    The paper studies perturbed and conservative model-based planning for discounted infinite-horizon MDPs, and plain model-based planning for time-inhomogeneous finite-horizon MDPs.

  • Results

    The proposed approaches achieve minimax-optimal sample complexity for the full accuracy range, with infinite-horizon guarantees beginning at order |S||A|/(1−γ) and finite-horizon guarantees at order |S||A|H^2, up to logarithmic factors.

  • Takeaways & Limitations

    The results broaden the known sample-size range enough to characterize a complete trade-off between sample complexity and statistical accuracy for these MDP settings.

  • Takeaways & Limitations

    For infinite-horizon MDPs, it remains unresolved whether plain model-based planning without perturbation or conservative action selection achieves optimal performance, and tight analysis for time-homogeneous finite-horizon MDPs is also unclear.

Abstract

from arXiv · show

This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator). We first consider $γ$-discounted infinite-horizon Markov decision processes (MDPs) with state space $\mathcal{S}$ and action space $\mathcal{A}$. Despite a number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy is yet to be determined. In particular, all prior results suffer from a severe sample size barrier, in the sense that their claimed statistical guarantees hold only when the sample size exceeds at least $\frac{|\mathcal{S}||\mathcal{A}|}{(1-γ)^2}$. The current paper overcomes this barrier by certifying the minimax optimality of two algorithms -- a perturbed model-based algorithm and a conservative model-based algorithm -- as soon as the sample size exceeds the order of $\frac{|\mathcal{S}||\mathcal{A}|}{1-γ}$ (modulo some log factor). Moving beyond infinite-horizon MDPs, we further study time-inhomogeneous finite-horizon MDPs, and prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level. To the best of our knowledge, this work delivers the first minimax-optimal guarantees that accommodate the entire range of sample sizes (beyond which finding a meaningful policy is information theoretically infeasible).

1 Introduction

The paper addresses sample-efficiency gaps in model-based reinforcement learning with a generative model, especially barriers that leave the low-sample regime theoretically unresolved. It proposes minimax-optimal methods covering broader sample-size and accuracy ranges in both infinite- and finite-horizon MDPs.

  • Problem setting: The paper studies model-based RL with a generative model that supplies samples for each state-action pair, including sub-linear sampling where accurate model estimation is generally infeasible.The total sample size is smaller than the number of model parameters in this regime.
  • Motivation: sample size barriers: Prior model-based results required total sample size at least |S||A|/(1−γ)^2, leaving a gap between upper and lower bounds below that barrier.Related model-free results faced an even more severe |S||A|/(1−γ)^3 barrier.
  • Contributions: Two algorithms—perturbed model-based planning and conservative model-based planning—find ε-optimal policies once the sample size exceeds order |S||A|/(1−γ), up to logarithmic factors.They match the minimax lower bound and cover the full stated accuracy range.
  • Contributions: The infinite-horizon guarantees cover the full range of accuracy levels ε ∈ (0, 1/(1−γ)], including sample sizes sufficient to find a policy strictly better than random guessing.The paper also derives minimax-optimal policy-evaluation guarantees over a broader sample-size range.
  • Contributions: For time-inhomogeneous finite-horizon MDPs, plain model-based planning achieves minimax-optimal sample complexity for every target accuracy level without perturbation or conservative action selection.The paper positions this result against prior finite-horizon comparisons summarized in Table 2.
  • Technical approach: The proofs combine high-order value-estimation expansions with fine-grained term analysis, policy-data dependency control, reward-perturbation tie breaking, and finite-horizon variance control.The dependency argument uses auxiliary state-action-absorbing MDPs.

2 Problem formulation

The paper formulates model-based planning for discounted infinite-horizon and time-inhomogeneous finite-horizon MDPs under generative-model sampling. It defines the corresponding empirical MDPs, policy objectives, value ranges, and notation used for accuracy and sample-complexity analysis.

  • 2.1 Discounted infinite-horizon Markov decision processes: A discounted infinite-horizon MDP is specified by finite state and action spaces, discount factor γ, normalized rewards, and a transition kernel P.The model is represented as M = (S, A, P, r, γ).
  • 2.1 Discounted infinite-horizon Markov decision processes: A deterministic policy maps each state to an action, while its value and Q-functions measure expected discounted rewards from states and state-action pairs.An optimal policy simultaneously maximizes these quantities across all states and state-action pairs.
  • 2.1 Discounted infinite-horizon Markov decision processes: The generative model provides N independent transition samples for every state-action pair, yielding an empirical transition kernel and empirical MDP.The total sample size is N|S||A|, and the empirical kernel records transition frequencies.
  • 2.1 Discounted infinite-horizon Markov decision processes: Infinite-horizon policy learning seeks an ε-accurate policy whose value and Q-function are within ε of their optimal counterparts, with ε ranging over the normalized value scale.With rewards in [0,1], values lie in [0,1/(1−γ)].
  • 2.1 Discounted infinite-horizon Markov decision processes: Standard model-based planning plugs the empirical MDP into Bellman recursion for policy evaluation or planning, including methods such as Q-value iteration and policy iteration.Policy evaluation separately targets approximation of a fixed policy’s value function.
  • 2.2 Finite-horizon Markov decision processes: A finite-horizon MDP uses time-indexed transition kernels and rewards over H steps, with policies that may select different actions at different time steps.The model is time-inhomogeneous when the kernels vary across steps.
  • 2.2 Finite-horizon Markov decision processes: Finite-horizon generative sampling provides N independent samples for every state-action-time triple and constructs an empirical MDP from the corresponding transition frequencies.The total sample size is NH|S||A|.
  • 2.2 Finite-horizon Markov decision processes: Finite-horizon policy learning targets an ε-accurate policy, while normalized rewards place value and Q-functions in [0,H] and therefore set ε ∈ [0,H].The notation section defines asymptotic bounds, logarithm-suppressed bounds, vector operations, and matrix norms.

3 Model-based planning in discounted infinite-horizon MDPs

The paper develops two model-based planning algorithms that overcome prior sample-size barriers for discounted infinite-horizon MDPs, with guarantees spanning the meaningful accuracy and sample-size regimes. It also establishes matching policy-evaluation guarantees and shows that the approaches achieve minimax-optimal performance.

  • Motivation and gap: Prior theory required at least |S||A|/(1−γ)^2 samples, leaving the range N ∈ [1/(1−γ)^2] theoretically unresolved.The prior barrier affected model-based planning and policy evaluation, while lower bounds did not rule out meaningful accuracy below it.
  • Algorithms: The perturbed algorithm plans in an empirical MDP after adding mild random reward perturbations, without requiring additional samples.The perturbation is applied during planning, and empirical QVI or policy iteration can recover the perturbed empirical optimum.
  • Algorithms: The conservative algorithm selects approximately optimal empirical-MDP actions within a randomized gap instead of always selecting empirical optima.For each state, it chooses the smallest-index action whose empirical action value lies within the sampled gap from optimal.
  • Comparison and implications: The results certify minimax-optimal model-based performance across the full sample-size and accuracy ranges previously unavailable in theory.The paper identifies the below-barrier regime as information-theoretically meaningful until the point where learning a policy better than random guessing becomes infeasible.
  • Theoretical guarantees: The policy-evaluation result covers the full ε-range and matches the minimax lower bound up to a log log(1/(1−γ)) factor.The plug-in value estimate begins outperforming a random guess once the stated sample threshold is reached.

4 Model-based planning in finite-horizon MDPs

For finite-horizon MDPs, the paper uses ordinary model-based planning: estimate the empirical MDP and solve it by dynamic programming. This achieves nearly minimax-optimal accuracy across the full target-accuracy range, with sample complexity reflecting the horizon and time inhomogeneity.

  • Algorithm: Model-based planning constructs an empirical finite-horizon MDP and computes its optimal policy using backward dynamic programming.The method does not require reward perturbation in the finite-horizon setting.
  • Guarantee: The resulting policy is nearly minimax optimal for finite-horizon MDPs.The paper states this guarantee in Theorem 4.
  • Guarantee: ε-accuracy holds for every ε in (0, H] when the sample size per (s, a, h) exceeds the stated order, up to logarithmic factors.The effective horizon is H in this finite-horizon result.
  • Guarantee: The total sample complexity scales with |S||A|H combinations and has H^4 dependence because transitions may differ across time steps.Time inhomogeneity contributes an additional factor of H relative to the discounted infinite-horizon case.

5 Other related works

The related-work discussion situates the paper against non-asymptotic RL, generative-model analyses, and prior model-based guarantees. Earlier results improved progressively but did not cover the full sample-size range addressed here.

  • Background: Recent RL theory shifted from asymptotic analysis toward non-asymptotic and finite-time performance guarantees.The cited literature uses concentration inequalities and studies finite-sample behavior.
  • Generative models: Generative models provide a simulator-based framework used across many model-based and model-free RL analyses.The paper traces this framework to Kearns and Singh (1999).
  • Prior model-based results: Earlier model-based results could estimate optimal Q-functions efficiently, but translating those guarantees to policy learning introduced additional sample-complexity factors.The discussion contrasts Q-function estimation with policy guarantees.
  • Prior model-based results: Agarwal et al. (2020) extended model-based guarantees to sample sizes beginning at |S||A| log(|S||A|)/(1−γ)^2, but the present analysis develops further techniques to complete the picture.The paper identifies state-absorbing MDPs as part of the motivation for its analysis.
  • Analytical framework: Leave-one-out analysis has been applied to decouple statistical dependencies in MDPs and later generalized to offline RL, linear function approximation, and Markov games.The paper attributes the MDP application to Agarwal et al. (2020).

6 Analysis: infinite-horizon MDPs

The infinite-horizon analysis combines matrix-based Bellman identities with high-order error expansions and auxiliary MDP constructions. These tools control policy-dependent estimation errors and support guarantees for perturbed and conservative model-based planning.

  • Matrix notation: The analysis represents rewards, value functions, Q-functions, and transition kernels in matrix form to express Bellman consistency equations.The transition matrix has one row for each state-action pair, while policy-induced matrices describe transitions under a policy.
  • Policy evaluation: Policy evaluation compares true and empirical value functions through resolvent identities and progressively higher-order expansions of their estimation error.Higher-order terms enable finer control than separately bounding the basic decomposition.
  • Policy evaluation: The analysis strengthens prior policy-evaluation guarantees with an instance-dependent bound and broader applicability across sample sizes.The paper reports matching a prior result up to logarithmic factors under noiseless rewards while extending the applicable range.
  • Policy-dependent analysis: A generalized Bernstein-type analysis applies even when the policy depends statistically on the empirical transition model, provided the dependency is sufficiently weak.This step enables subsequent analysis of the empirical optimal policy.
  • Decoupling statistical dependence: State-action-absorbing auxiliary MDPs and leave-one-row-out arguments decouple the empirical optimal policy from the transition-row data used to analyze it.Unlike state-absorbing constructions, a state-action-absorbing MDP makes a state absorbing only for a designated action.
  • Tie-breaking: Random reward perturbations create action-value separation by breaking ties, allowing the perturbed planning analysis to handle MDPs lacking a separation condition.The perturbation is designed to produce a nearby MDP satisfying the needed separation condition.
  • Conservative planning: The same analytical framework supports the conservative model-based approach without reward perturbation.The conservative policy construction yields a representation independent of the randomness associated with a state-action pair.

7 Analysis: finite-horizon MDPs

The finite-horizon analysis extends the paper’s matrix and recursive value-function tools to time-indexed transitions. Backward computation creates the independence structure needed to establish the model-based planning guarantee.

  • Finite-horizon notation: Finite-horizon notation represents time-indexed rewards, transition kernels, policy-restricted transitions, and value functions at each step h.These objects support Bellman equations analogous to the infinite-horizon analysis.
  • Recursive analysis: The analysis defines recursive auxiliary value sequences whose zeroth terms equal the true and empirical value functions of a policy.Bernstein-type conditions on the sequences yield entrywise bounds on their differences.
  • Proof strategy: The proof verifies Bernstein-type conditions separately for the fixed optimal policy and the empirical optimal policy before applying the recursive lemma.For the fixed policy, independence from the data gives the condition directly; the empirical policy requires the backward structure.
  • Recursive analysis: Backward dynamic programming makes the policy at step h independent of empirical transitions from earlier steps, enabling the required concentration arguments.This independence lets the preceding recursive bounds continue to hold for the empirical optimal policy.
  • Proof strategy: Substituting the resulting bounds proves the finite-horizon guarantee with probability greater than 1−2δ under the stated sample-size condition.The final step chooses the sample size so the bound is at most ε.

8 Discussion

The paper broadens minimax-optimal sample-complexity guarantees for model-based planning, while identifying open questions about applicability beyond the studied settings and about simplifying the infinite-horizon algorithms.

  • Main conclusion: The results broaden the sample-size range in which model-based planning achieves minimax sample complexity and complete the sample-complexity–accuracy trade-off.For discounted infinite-horizon MDPs, the threshold is order 1/(1−γ), while for time-inhomogeneous finite-horizon MDPs it is |S||A|H^2, up to logarithmic factors.
  • Open questions: For infinite-horizon MDPs, whether perturbation or conservative action selection is necessary remains unresolved.The paper conjectures that plain empirical-MDP planning may achieve optimal performance, but settling this requires techniques beyond its analysis framework.
  • Scope and limitations: Tight sample-complexity analyses remain open for model-free methods, time-homogeneous finite-horizon MDPs, Markovian trajectories, and online exploratory RL.The discussion identifies these settings as directions for extending the current theory.
  • Scope and limitations: The analysis is restricted to tabular finite-state, finite-action MDPs, so sample complexities may remain prohibitive when |S| and |A| are enormous.The paper points to low-complexity function approximation as a direction for improving efficiency.

B.1 Proofs of Lemma 1 and Lemma 2

These proofs establish technical bounds for value-function perturbations by combining recursive decompositions, improved variance control, and concentration inequalities under sufficient per-state-action sampling.

  • Variance control: An improved variance bound for ∥(I−γP^π)^−1√Var_Pπ(V)∥∞ replaces a looser prior bound and supports the subsequent error analysis.
  • Error control: The recursive inequalities control separate error terms α1 and α2, with geometric-series arguments requiring sufficiently large N relative to β1/(1−γ).The proof explicitly uses conditions such as N ≥ 64β1/(1−γ) and N > 16e^2 times the relevant logarithmic factor.
  • Concentration: Bernstein concentration applies because the relevant value vectors are independent of the empirical transition operators being conditioned on.A union-bound argument yields uniform control over the recursive terms with high probability.
  • Absorbing-MDP construction: The proof verifies Bellman optimality equations for an absorbing MDP construction, showing that the constructed optimal values match those of the original MDP.

B.4 Proof of Lemma 5

The proof of Lemma 5 combines uniform concentration over an epsilon-net with policy independence and prior lemmas to establish the advertised high-probability value bound.

  • Epsilon-net construction: The proof constructs an epsilon-net over the perturbation parameter and considers optimal policies for the corresponding absorbing MDPs.
  • Uniform concentration: The constructed policies are independent of the empirical transition kernel for each state-action pair, enabling Bernstein concentration and a union bound.The resulting event holds simultaneously over all net points and state-action pairs.
  • Net approximation: For every state-action pair, a nearby epsilon-net point induces the same optimal policy as the target perturbation, allowing the net-based bound to transfer to the desired policy.
  • Conclusion: Under the stated sample-size and perturbation conditions, Lemma 2 yields the advertised bound, which is then combined with Lemma 1 and prior relations to prove Lemma 5.

B.5 Proof of Lemma 6

The proof of Lemma 6 bounds the measure of perturbation values where the optimal action is insufficiently separated, splitting the analysis around a phase-transition threshold.

  • Setup: The proof varies one perturbed reward while freezing all other rewards, then studies how the optimal value and policy change with that scalar parameter.
  • Phase transition: A phase-transition boundary τ_th separates the parameter ranges in which the perturbed action is or is not optimal.
  • Interval bounds: The lower parameter interval has Lebesgue measure at most 2ω because the relevant optimal value does not vary with the perturbed reward there.
  • Interval bounds: The upper interval is bounded by comparing value differences across reward parameters and showing values sufficiently above τ_th+ω cannot belong to the near-tie set.

B.6 Proof of Lemma 7

The proof constructs a modified-reward MDP to show that the conservative policy attains the target optimal value, then establishes the lemma through Bellman relations and set inequalities.

  • Modified-reward construction: The proof introduces a modified reward that adds the optimality gap when the conservative policy selects an action.For a = bπc(s), the reward becomes r(s, a) + bV⋆(s) − bQ⋆(s, a); otherwise it remains r(s, a).
  • Modified-reward construction: The constructed eQ and bV⋆ satisfy the Bellman optimality condition for the modified MDP.The argument uses bQ⋆ = r + γbP bV⋆ and the modified reward construction to identify the optimal Q- and value functions.
  • Policy value: The conservative policy’s value in the modified MDP equals bV⋆.This follows because eQ and bV⋆ are optimal for the modified MDP and the policy-specific value satisfies eV bπc = bV⋆.
  • Set inequalities: The remaining proof uses Bellman-based identities, uniform perturbation bounds, and a decomposition of bV(s) − bQ(s, ba) to establish the lemma’s set inequalities.The argument handles actions above and below the threshold V(s) − ς and concludes after combining the two resulting inequalities.
  • Set inequalities: The two action-set inequalities together establish the lemma.The proof separately treats actions satisfying Q(s, a) > V(s) − ς and Q(s, a) ≤ V(s) − ς, then combines the results.

C Proofs of auxiliary lemmas: finite-horizon MDPs

The auxiliary finite-horizon proofs control value-function magnitudes and recursively bound transition and estimation terms across stages, using concentration, norm inequalities, and sample-size assumptions.

  • Value-function control: The proof first establishes entrywise bounds for the finite-horizon value iterates V^(l)_h across all stages and iterations.The corresponding control is stated as a lemma whose proof is deferred to Section C.2.
  • Recursive bounds: The analysis applies the construction for l ≤ m := log2 H and substitutes the resulting relations into successive inequalities.These substitutions connect the recursive stagewise bounds to the displayed estimates used later in the proof.
  • Recursive bounds: Recursive relations propagate bounds across stages by combining transition-matrix properties, triangle inequalities, and the construction of r^(l).The proof uses that transition matrices preserve the relevant norm and repeatedly applies the resulting recursion.
  • Final estimates: Jensen’s inequality, Cauchy–Schwarz, telescoping summation, and the construction of r^(l) combine to produce the final recursive estimates.The final step also invokes the relation for V^(l)_j and a trivial upper bound on the initial value iterate.
  • Sample-size conditions: The proof controls the remaining terms through elementary bounds and the assumptions N ≤ 1/2 and N ≥ 12Hβ1.It concludes under the proviso N ≥ 3β1H.
  • Final estimates: The resulting inequalities yield the desired bound after applying the relation for V^(l)_j and bounding the initial iterate.The proof identifies the specific inequality used for the penultimate step and then applies the upper bound on max_j ∥V^(0)∥.
Loading 2005.12900v8…