PAC Bounds for Discounted MDPs

Tor Lattimore; Marcus Hutter

Source-linked AI summary

PAC Bounds for Discounted MDPs

Tor Lattimore, Marcus Hutter

arXiv:1202.3890v1Feb 17, 2012cs.LG

TL;DR

The paper asks how many time-steps are needed to learn near-optimal behavior in finite-state discounted MDPs with unknown transitions. It modifies UCRL for a two-next-state setting and develops a general lower-bound construction. The resulting upper and lower PAC bounds match up to logarithmic factors, while the lower bound improves prior work in size and generality.

Problem
The paper studies PAC sample-complexity for learning near-optimal behavior in finite-state discounted MDPs with unknown transitions.
Method
The paper modifies UCRL using optimistic model selection and knownness-based updates, and constructs a lower-bound MDP with a delaying state that removes policy restrictions.
Results
The upper and lower PAC bounds match up to logarithmic factors, while the lower bound is larger and more general than previous work.
Takeaways & Limitations
The results improve known PAC bounds for discounted MDPs, with the upper bound applying under a two-next-state assumption and the lower bound applying generally.
Takeaways & Limitations
The new upper bound depends on an assumption that each state/action pair has at most two possible next-states, although the authors believe it is probably unnecessary.

Abstract

from arXiv · show

We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (MDPs). For the upper bound we make the assumption that each action leads to at most two possible next-states and prove a new bound for a UCRL-style algorithm on the number of time-steps when it is not Probably Approximately Correct (PAC). The new lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors.

1 Introduction

The paper studies PAC sample-complexity in finite-state discounted MDPs with unknown transitions, modifying UCRL under a two-next-state assumption. It improves prior bounds and gives a larger, more general matching lower bound.

The study measures near-optimal learning by the number of time-steps when an algorithm is not PAC with high probability.
The modified UCRL algorithm obtains a new PAC upper bound when each state/action pair has at most two possible next-states.
The new upper bound improves on the previous best bounds in the restricted setting.
The lower bound is larger and more general than previous work, applying without policy restrictions and matching the upper bound up to logarithmic factors.

2 Notation

This section introduces notation for finite discounted MDPs, policies, values, transitions, and related true, estimated, and model-based MDP quantities.

The section also establishes conventions for natural numbers, indicators, logical operators, set sizes, logarithms, expectations, variances, and a progression used later.
An MDP is represented by finite state and action sets, a reward function, transition probabilities, and a discount rate γ.
A stationary policy maps each state to an action, while transition vectors describe next-state probabilities under state-action choices.
The value of a policy is defined for each state, and the optimal policy is denoted π*.
The notation distinguishes the true MDP, an empirically estimated MDP, and a model, with corresponding value functions V, bV, and eV.

3 Estimation

The estimation analysis explains why variance-sensitive concentration is useful for approximating value functions in discounted MDPs. Bernstein’s inequality can reduce the required visits compared with Hoeffding-based estimation.

The paper uses Bernstein’s inequality because it accounts for variance, unlike Hoeffding’s inequality.
In a two-state reward process, value-estimation accuracy depends on accurately estimating the transition probability p.
Hoeffding-based estimation requires more visits because achieving value error ǫ requires transition error below ǫ(1 − γ)^2.
When p > γ, Bernstein’s inequality reduces the sufficient visits to order L/[ǫ^2(1 − γ)^3], whereas the Hoeffding route is too large for a 1/(1 − γ)^3 bound.
When p < γ, the value-error relation can be improved further.

4 Upper Confidence Reinforcement Learning Algorithm

The modified UCRL algorithm uses optimistic model selection, confidence intervals, and a knownness index to manage exploration and updates. Its analysis relies on an assumption about transition probabilities.

UCRL chooses the most optimistic model inside a high-probability model class containing the true MDP.
Optimism biases exploration toward unknown states that may yield good rewards while avoiding states known to be bad.
The upper-bound proof requires an assumption on the true MDP’s transition probabilities, which substantially eases analysis by removing dependencies.
The knownness index κ increases with visits, is bounded by |S|, and triggers updates when state-action knownness changes.
The algorithm operates through episodes, delayed phases, updates, action execution, and optimistic extended value iteration.
Extended value iteration is established as an available procedure for returning an optimistic model and its policy.

5 Upper PAC Bounds

The paper presents two upper PAC bounds for UCRL: one improves prior analyses under Assumption 1, while a general bound adds a |S| dependence. The proof controls non-near-optimal time through optimistic models, confidence estimates, knownness, and exploration phases.

Upper bounds: Two new PAC bounds are presented: an assumption-dependent bound and a completely general bound with dependence on |S|2 and 1/(1 −γ)3.The general bound is worse than the previous best in |S| but better in 1/(1 −γ).
Upper bounds: Theorem 3 bounds the non-near-optimal time-steps of UCRL when the true MDP satisfies Assumption 1.The theorem applies to UCRL’s actual non-stationary policy.
Upper bounds: For arbitrary MDPs, Theorem 4 gives a bound scaling with |S| log^3 |S|(EmaxH + UmaxH) time-steps.The proof converts an arbitrary |S|-state MDP into an equivalent O(|S|2)-state MDP satisfying Assumption 1, then rescales γ.
Proof strategy: UCRL uses optimistic model selection, confidence sets, knownness-triggered updates, and analysis-only exploration phases to control learning time.Non-near-optimal behavior is linked to a discrepancy between true and model values, which implies information gain during exploration.
Proof strategy: The analysis relies on stationary behavior within non-delaying horizons even though UCRL’s global policy is non-stationary.Episodes end when knownness changes, and exploration phases are used only in the analysis.
Proof strategy: The proof bounds delayed and exploration phases separately, yielding at most HUmax + HEmax non-near-optimal time-steps with probability 1 −δ.The number of updates is bounded by Umax, while exploration phases are bounded by Emax.

6 Eliminating the Assumption

The paper explains why removing Assumption 1 is difficult: the required confidence constraints can depend on higher moments, estimated transition probabilities, and globally coupled model choices. It reports progress for lower-moment constraints but leaves the full generalization unresolved.

Challenges: The upper-bound analysis uses Assumption 1 to control transition-model errors, and removing it requires adding more complex constraints to the model class.The paper states that the assumption is probably unnecessary but substantially eases the analysis.
Challenges: A key obstacle is that the optimistic value function depends on estimated transitions, violating the independence condition needed for Bernstein’s inequality.The paper describes this dependence as intuitively weak but problematic for a rigorous proof.
Challenges: Additional constraints are non-local because they depend on transition choices for other state-action pairs, complicating extended value iteration.The authors describe this complication as probably resolvable, but no formal demonstration is supplied here.
Progress: Bernstein-based constraints on first and second value moments suffice for Lemma 8, whereas higher-moment constraints make extended value iteration substantially more complex.The complete proof of Lemma 8 uses higher moments, although the authors state they are not required.

7 Lower PAC Bound

The lower-bound construction applies to arbitrary policies and strengthens prior results by adding a delaying state, yielding a tighter dependence on 1/(1−γ)^3.

Lower-bound refinements: The construction improves the previous lower bound by depending on 1/(1−γ)^3 and removing policy restrictions.A delaying state provides time during which no information is gained while the algorithm may still fail to be PAC.
Theorem 15: The lower bound applies to any possibly non-stationary policy depending on S, A, r, γ, ǫ, and δ.There exists a hard MDP where the policy is more than ǫ-suboptimal for at least N time-steps with probability at least δ.
Counter-example: The hard MDP has four states, with one optimal action in state 1 that is slightly more likely to transition to the maximally rewarding state ⊕.States ⊕ and ⊖ are nearly absorbing and provide maximum and minimum rewards, respectively.
Counter-example: State 0 keeps a policy there for about 1/(1−γ) time-steps on average, amplifying mistakes planned for the later decision state.Although every action is optimal in state 0, the value loss is measured over the policy’s eventual behavior in state 1.
Intuition: The construction is bandit-like because learning which action is best in state 1 reduces to identifying the action most likely to reach ⊕.Bandit sample-complexity results are used to lower-bound the number of times the optimal action is not selected.

8 Conclusion

The paper gives matching upper and lower PAC bounds up to logarithmic factors in the restricted setting, while the lower bound remains general. The upper bound requires at most two possible next-states per state/action pair, and the running time is left unanalyzed.

Summary: The upper and lower bounds match in the restricted setting where each state/action pair has at most two possible next-states.The lower-bound counterexamples satisfy the assumption used for the upper bound.
Summary: The lower bound is assumption-free, larger and more general than Strehl et al. (2009), while the upper bound improves on Auer (2011) under its transition assumption.Without the assumption, the new proof gives an algorithm with better dependence on 1/(1−γ) but worse dependence on |S|.
Running Time: The running time of the proposed UCRL version is not analyzed, although the authors expect a polynomial-time approximation without increasing sample complexity.This expectation is based on an analysis similar to Strehl and Littman (2008).

A Proof of Lower PAC Bound

The lower-bound proof reduces policy learning in a hard discounted MDP to bandit learning, then uses long phases to convert suboptimal action weight into many ε-errors.

Reduction: The proof applies a bandit sample-complexity lower bound to show that an arbitrary policy cannot be approximately correct in state 1 often enough.The hard MDP is used to transfer bandit difficulty to discounted MDP behavior.
Phase construction: The construction partitions visits to state 0 into phases whose lengths are independent of the policy and each other.Each phase begins on entering state 0 and ends when the process leaves for state 1.
Phase construction: At least two thirds of phases have length at least 1/[4(1 −γ)] with high probability.The phase-length event Xi captures this lower-duration condition.
Error accumulation: If a phase starts with combined suboptimal-action weight at least 1/4, that weight persists throughout the phase.Event Ai additionally requires the phase length to be at least 1/[16(1 −γ)].
Error accumulation: Each phase satisfying Ai contributes at least 1/[16(1−γ)] ε-errors, and sufficiently many such phases occur with probability at least δ.The proof completes the lower bound by combining the phase lemmas.
State dependence: Dependence on S is added by chaining arbitrarily many copies of the hard Markov decision process.A possible S log S dependence is noted but its details are described as potentially messy.

B Technical Results

This section introduces Hoeffding and Bernstein inequalities as tools for controlling transition-probability estimation errors and combining confidence intervals.

Concentration bounds: Hoeffding and Bernstein inequalities are used to bound successive transition-probability estimation gaps.The analysis combines bounds on |p−p̂| and |p̂−p̃| to control |p−p̃|.
Confidence-interval combination: The proof combines two confidence intervals to derive a bound on the difference between the true and alternative transition probabilities.The derivation uses an ordering assumption and algebra before applying the first confidence interval.

C Proof of Lemma 8

The proof of Lemma 8 develops higher-moment value functions and bounds their components, replacing a insufficient naive bound with an approximation-based refinement.

Higher-moment construction: Higher “moment” value functions are introduced because they complicate the proof but may be unavoidable.These functions support the subsequent bounds used in Lemma 8.
Higher-moment construction: The proof defines bounded value/reward functions recursively through Bellman equations and corresponding estimated versions.The recurrence alternates the true reward function with higher-order variance-related quantities.
Completion: The final substitution into Equation (10) completes the proof of the lemma.
Component bounds: The components Bd and Cd are easier to bound than Ad, for which the proof first derives a naive bound.Cauchy–Schwarz and the boundedness assumption are used in the naive estimate.
Component bounds: The naive bound on the relevant variance term is insufficient, so the proof approximates w(s) by w̃(s) to improve the final step.The stated naive bound is d(s) ≤1/(1 −γ)2d+3.

D Constants

This section collects notation and constants for the MDP analysis, including state, action, transition, value, visitation, confidence, and indexing quantities.

MDP notation: The analysis uses finite state and action sets, a transition function p, rewards r, discount rate γ, and an accuracy parameter ε.
Auxiliary notation: Z(a) contains approximately log a elements, and L1 is defined as log(2/δ1).
MDP notation: The notation distinguishes the true MDP, empirically estimated MDP, and model-class MDP through M, M̂, and M̃.It also distinguishes their policy values and optimal policies.
Counts and policies: π_k denotes the stationary policy used in episode k, while s_t and a_t denote the state and action at time-step t.
Counts and policies: The symbols n_t(s,a), n_t(s,a,s′), and n_t(s) count visits to state-action pairs, transitions, and policy-selected actions.
Auxiliary notation: The analysis defines discounted visitation weights, an active state set, index sets K and I, logarithms, expectations, variances, and the confidence quantity δ.δ is the probability that an algorithm makes more mistakes than its sample-complexity.