Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning

Christoph Dann; Emma Brunskill

Source-linked AI summary

Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning

Christoph Dann, Emma Brunskill

arXiv:1510.08906v3Oct 29, 2015stat.MLcs.AIcs.LG

TL;DR

The paper addresses limited sample-complexity guarantees for episodic fixed-horizon reinforcement learning. It develops upper and lower PAC bounds using UCFH and obtains near-matching bounds with quadratic horizon dependence, while identifying scope limitations in the lower-bound parameter ranges.

Problem
Episodic fixed-horizon reinforcement learning lacked tight sample-complexity bounds despite its relevance to repeated finite-step decision problems.
Method
The paper develops UCFH, an optimism-under-uncertainty model-based algorithm that plans with confidence sets over transition parameters and updates its model across phases.
Results
The upper and lower PAC bounds are tight up to logarithmic factors in H, ϵ, and |A| and an additive constant in δ, improving existing results by at least a factor of H.
Takeaways & Limitations
UCFH applies directly to a wide range of fixed-horizon episodic MDPs with known rewards without requiring sparse or acyclic transitions.
Takeaways & Limitations
The lower bound applies only over δ and ϵ ranges whose limits are largely inherited from the underlying bandit result.

Abstract

from arXiv · show

Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-world applications, an interactive learning agent operates for a fixed or bounded period of time, for example tutoring students for exams or handling customer service requests. Such scenarios can often be better treated as episodic fixed-horizon MDPs, for which only looser bounds on the sample complexity exist. A natural notion of sample complexity in this setting is the number of episodes required to guarantee a certain performance with high probability (PAC guarantee). In this paper, we derive an upper PAC bound $\tilde O(\frac{|\mathcal S|^2 |\mathcal A| H^2}{ε^2} \ln\frac 1 δ)$ and a lower PAC bound $\tilde Ω(\frac{|\mathcal S| |\mathcal A| H^2}{ε^2} \ln \frac 1 {δ+ c})$ that match up to log-terms and an additional linear dependency on the number of states $|\mathcal S|$. The lower bound is the first of its kind for this setting. Our upper bound leverages Bernstein's inequality to improve on previous bounds for episodic finite-horizon MDPs which have a time-horizon dependency of at least $H^3$.

1 Introduction and Motivation

The paper studies sample complexity for episodic fixed-horizon reinforcement learning, where agents repeatedly make decisions over a fixed number of steps. It introduces bounds and an algorithm that improve horizon dependence without requiring special transition structure.

1 Introduction and Motivation: Episodic fixed-horizon reinforcement learning models repeated finite-step decision problems with unknown domain parameters.Examples include tutoring students for exams and maximizing business revenue over quarters.
1 Introduction and Motivation: The paper presents the first lower bound and a new upper bound for PAC reinforcement learning in discrete state-action spaces.The bounds are tight up to specified logarithmic factors and an additive constant in failure probability.
1 Introduction and Motivation: UCFH applies to fixed-horizon episodic MDPs with known rewards without requiring generative models or sparse or acyclic transitions.This broadens direct applicability to generic finite-horizon MDPs.
1 Introduction and Motivation: The upper bound scales as H^2 episodes, improving on prior approaches with at least H^3 dependence.Earlier related results also required stationary optimal policies or had at least H^4 dependence.
1 Introduction and Motivation: The analysis combines a Bellman equation for value-function variance with precision estimates adapted to state-action visitation under nonstationary policies.These ideas support the quadratic horizon dependence in the finite-horizon setting.

2 Problem Setting and Notation

The problem setting is a finite episodic MDP with finite states and actions, horizon H, known rewards, and unknown stationary transitions. Policies may depend on the within-episode timestep, and PAC complexity counts episodes with non-ϵ-optimal behavior.

2 Problem Setting and Notation: An episodic fixed-horizon MDP is defined by finite state and action sets, transition and reward models, an initial-state distribution, and horizon H.The agent interacts for H steps per episode, receiving rewards and sampling subsequent states from the transition kernel.
2 Problem Setting and Notation: Policies may be nonstationary, selecting actions as a function of both the current state and within-episode timestep.The best action can change as the number of remaining steps changes.
2 Problem Setting and Notation: The analysis assumes known rewards and an unknown transition kernel.This follows prior analyses because learning state transitions usually dominates learning reward functions; unknown rewards are stated to be extendable.
2 Problem Setting and Notation: PAC sample complexity asks how many episodes the learner follows a policy that is not ϵ-optimal, with probability at least 1 − δ.The accuracy ϵ and failure probability δ are user-selected.
2 Problem Setting and Notation: The maximum number of possible successor states for any state-action pair is denoted C, with C = |S| absent additional assumptions.This captures transition-support size in the notation.

3 Upper PAC-Bound

UCFH combines optimism, finite-horizon planning, and variance-sensitive confidence sets to learn episodic MDPs with a quadratic horizon dependence. Its analysis yields high-probability ε-optimal policies while supporting nonstationary policies and generic successor structures.

UCFH algorithm: UCFH alternates optimistic planning, policy execution, and model updating in episode-level phases.It computes policies with a finite-horizon variant of extended value iteration and updates statistics when a state-action pair is sufficiently visited.
Model class: UCFH directly handles time-dependent policies and non-sparse transitions without requiring a generative model or sparse or acyclic dynamics.The true stationary MDP remains in the confidence set even though time-dependent transitions are allowed for computationally efficient optimistic planning.
Confidence sets: UCFH uses confidence sets combining Hoeffding, Bernstein, and empirical-variance conditions for transition probabilities.The additional variance-matching condition supports generic MDPs while keeping the PAC bound linear in the maximum number C of successor states.
PAC guarantee: With probability at least 1 − δ, UCFH produces at most a bounded number of non-ε-optimal episodes, yielding the stated upper PAC guarantee.The proof combines confidence-set coverage, optimistic planning, bounds on phases with insufficiently known important state-action pairs, and reward-mismatch control.
Variance analysis: O(H^2) bounds the total sum of local value-function variances, replacing the trivial O(H^3) bound in the analysis.The proof uses a Bellman equation for finite-horizon value variances, including time-dependent transitions and rewards.
Comparison and contribution: The resulting upper-bound analysis improves existing finite-horizon approaches by at least a factor of H and avoids the C = 2 restriction used in related work.The added confidence-set condition makes the reward-difference terms either variance-dependent or linearly decreasing with samples, producing linear dependence on C.

4 Lower PAC Bound

The paper establishes a lower sample-complexity bound for episodic fixed-horizon PAC reinforcement learning using hard MDPs that embed multiple bandit problems. The analysis accounts for episode-level optimality by requiring the policy to solve a sufficient portion of the embedded bandits.

Theorem 2 gives a lower bound for every PAC algorithm that outputs a deterministic policy on a suitable fixed-horizon episodic MDP.The result applies for sufficiently small accuracy ϵ and failure probability δ.
The lower-bound ranges for δ and ϵ are similar in order to those used in contemporary lower bounds for multi-armed bandits and discounted MDPs.The stated parameter ranges are largely inherited from the bandit result on which the construction builds.
The hard MDP starts from an initial state and reaches n states uniformly, with each state encoding a separate multi-armed bandit.The transition structure makes the unknown optimal action potentially different for each state.
Episode-level optimality requires solving at least a certain portion of all embedded bandits with probability at least 1 −δ.A suboptimal action in one bandit does not necessarily make the entire episode suboptimal, so the analysis averages across bandits.
The lower-bound strategy solves all embedded bandits with equal probability, and the required samples yield the lower bound in Equation (3).

5 Related Work on Fixed-Horizon Sample Complexity Bounds

Prior fixed-horizon analyses use alternative evaluation settings or additional assumptions, and their horizon dependence is generally weaker than the paper’s H^2 dependence. The paper argues these results do not directly match episodic whole-episode optimality.

Existing timestep-based approaches partition trajectories into fixed segments or use sliding windows, with horizon dependence of at least H^3 in episode counts.
Whole-episode evaluation is more natural for episodic MDPs because late suboptimal actions may be acceptable when total episode reward remains sufficiently high.
Timestep-based lower PAC bounds cannot be applied directly to the episodic reward criterion.
Other episode-based results use discounted horizons, no-regret guarantees, or structural assumptions such as acyclic transitions and known state-visitation probabilities.The latter bound explicitly depends on 1/q, and the assumptions are described as limiting.

6 Conclusion

The paper concludes that its upper and lower PAC bounds for episodic fixed-horizon reinforcement learning are closely matched in key parameters and improve the horizon dependence of prior results. UCFH applies broadly to known-reward domains without requiring sparse or acyclic transitions.

The upper and lower bounds are tight up to logarithmic factors in H, ϵ, and |A|, and up to an additive constant in δ.
The bounds improve existing results by at least a factor of H.
UCFH’s upper PAC guarantee can be applied to a wide range of fixed-horizon episodic MDPs with known rewards.
UCFH does not require sparse or acyclic state transitions assumed by some previous work.
The paper notes that empirical evaluation of UCFH remains an interesting direction for future work.

Appendices

The appendices describe FixedHorizonEVI, the optimistic planning routine used within UCFH, and provide runtime, space, and correctness statements. The routine constructs optimistic transitions from confidence sets and solves the resulting finite-horizon MDP by dynamic programming.

A Fixed-Horizon Extended Value Iteration: FixedHorizonEVI computes an optimistic MDP and policy by maximizing future value over transition probabilities compatible with confidence sets.
A Fixed-Horizon Extended Value Iteration: The feasible transition set uses probability distributions whose components lie in the convex hulls of the corresponding confidence sets.
A Fixed-Horizon Extended Value Iteration: Dynamic programming proceeds backward from the terminal reward, selecting actions and transitions that maximize the relevant Q-values.
A Fixed-Horizon Extended Value Iteration: The implementation allocates probability mass preferentially to successor states with the highest value.
A Fixed-Horizon Extended Value Iteration: Confidence sets may be unions of two disjoint intervals, but their minima and maxima remain computable in constant time.
A Fixed-Horizon Extended Value Iteration: Given sorted states, FixedHorizonEVI runs in O(H|S| log |S| + H|S||A|C) time and requires O(H|S||A|C) additional space.
UCFH complexity: Sampling one episode costs O(H), while policy updates call FixedHorizonEVI and contribute additional runtime terms.
UCFH complexity: Theorem 1 states that after the specified number of observed episodes, the current policy is ϵ-optimal with sufficiently high probability.

C Detailed Proofs for the Upper PAC Bound

The proof bounds the total number of updates by charging multiplicative increases in visitation counts separately to each state-action pair.

Umax bounds the total number of updates by a logarithmic factor times |S × A|.The bound follows because updates stop once every n(s, a) reaches the threshold |S|mH.
Each update increases exactly one state-action count by max{mwmin, n(s, a)}.Thus, each pair can be updated only logarithmically many times between the lower and upper count thresholds.
For one state-action pair, the number of updates is at most log2(|S|mH) − log2(mwmin).

C.2 Proof of Lemma 1 – Capturing the true MDP

The proof combines concentration inequalities, update-count control, and variance-based value-function arguments to capture the true MDP with high probability.

Bernstein’s inequality complements Hoeffding’s inequality for estimating successor-state probabilities.The proof applies both concentration bounds and combines their failure probabilities using a union bound.
The proof considers at most UmaxC distinct probability estimates across updates and successor states.Setting δ1 = δ 2CUmax yields the desired simultaneous high-probability event.
State-action pairs are grouped by importance κ and ι, with observations bounded by 3|S × A|mwι/κ.The weight wι is the smallest possible weight for pairs with importance ι, and wι+1 = 2wι.
The variance of the finite-horizon value function satisfies a Bellman equation with local variances.This variance recursion supports the value-estimation argument used in the proof.

C.4.2 Proof of Lemma 4 (Bellman equation of local value function variances)

The proof establishes a Bellman equation for local value-function variances and uses recursive bounds to control their contribution to value-estimation error.

The local variance function satisfies a Bellman equation obtained by unrolling conditional expectations.The proof uses the tower property and the terminal condition Vj:j(s) = 0.
The variance is bounded between zero and H^2rmax^2.
The recursive error bound expands into terms whose horizon dependence is controlled by the dominant term.The proof notes that C′d has the larger exponent of H compared with Bd and therefore dominates for sufficiently large m.
The proof imposes sufficient conditions on m1 to ensure Δ0 ≤ ϵ.These conditions include logarithmic factors involving γ and H.

C.5 Proof of Theorem 1

Theorem 1 combines bounds on exceptional episodes, model capture, and value estimation to guarantee near-optimal performance with probability at least 1 − δ.

With probability at least 1 − δ/2, episodes with |Xκ,ι| > κ are bounded by 6Emax|S × A|m.
For all other episodes, the estimated policy satisfies R∗ − Rπk < ϵ with probability at least 1 − δ/2.The proof uses Lemma 3 for value approximation and Lemma A.1 to compare the optimistic model value with R∗.
The required episode count m is selected so that the stated high-probability guarantee holds.

D Proof of the Lower PAC Bound

The lower-bound proof constructs an MDP from parallel multi-armed bandits, then uses independent success events and an optimization over per-state failure probabilities to derive the required episode count.

Hard-instance construction: The hard MDP consists of n parallel multi-armed bandits, each with |A| possible hypotheses differing in which action has an additional bias.Hypothesis I_i=0 gives only action a0 a small bias, while I_i=j adds bias to action aj.
Probability argument: The events that the policy chooses optimally in each bandit are independent, so their sum follows a Poisson-binomial distribution.This yields per-state failure bounds δ_i that must hold across all hypotheses while satisfying a collective accuracy constraint.
Accuracy requirement: At least a fraction φ := 1 − η/(8e4) of the bandits must be solved optimally for the resulting policy to be ε-accurate.The proof sets ϵ′ := 16ϵe4 (H−2)η and uses this requirement to obtain the lower bound.
Optimization: The proof minimizes the total required observations over per-state failure probabilities δ_1,...,δ_n, using convexity and KKT conditions to characterize the optimum.The analysis shows equal allocation δ_1 = ··· = δ_n = c is optimal under the stated condition.
Episode lower bound: η = 1/10 satisfies the sufficient condition, making the equal allocation optimal; because each episode observes only one state, the resulting observation requirement translates directly into episodes.Substituting ϵ′ and n = |S| − 3 gives the desired lower-bound statement.