PaperlayerView exact revision on arXiv

Source-linked AI summary

Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited

Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, Michal Valko

arXiv:2010.03531v1cs.LGstat.ML

TL;DR

The paper addresses lower bounds on sample complexity and regret in episodic MDPs, including settings with stage-dependent transitions. It develops a shared hard-MDP construction and provides a detailed proof of the Ω(√(H^3SAT)) regret lower bound.

  • Problem

    Minimax lower bounds help assess how episodic reinforcement-learning sample complexity and regret scale with H, S, and A.

    Source: §1 · p. 1

  • Method

    The paper uses a shared class of hard MDPs and information-theoretic arguments to prove lower bounds for episodic learning.

    Source: §1 · p. 2

  • Results

    The paper provides a detailed proof of the Ω(√(H^3SAT)) regret lower bound for stage-dependent transitions.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The same hard-MDP class supports the paper's sample-complexity and regret lower-bound proofs.

    Source: §1 · p. 2

    The proofs require a tree depth d no greater than H/3; when d > H/3, the bounds become exponential in H.

    Source: §6 · p. 14

Abstract

from arXiv · show

In this paper, we propose new problem-independent lower bounds on the sample complexity and regret in episodic MDPs, with a particular focus on the non-stationary case in which the transition kernel is allowed to change in each stage of the episode. Our main contribution is a novel lower bound of $\Omega((H^3SA/\epsilon^2)\log(1/\delta))$ on the sample complexity of an $(\varepsilon,\delta)$-PAC algorithm for best policy identification in a non-stationary MDP. This lower bound relies on a construction of "hard MDPs" which is different from the ones previously used in the literature. Using this same class of MDPs, we also provide a rigorous proof of the $\Omega(\sqrt{H^3SAT})$ regret bound for non-stationary MDPs. Finally, we discuss connections to PAC-MDP lower bounds.

1. Introduction

The paper develops minimax lower bounds for episodic reinforcement learning, addressing how sample complexity and regret scale with the horizon, state count, and action count. It introduces stage-dependent hard MDPs for best-policy identification and uses the same class to give a detailed regret proof.

1. Introduction

  • Lower bounds help assess minimax upper bounds, particularly their scaling with horizon H, state count S, and action count A.The introduction distinguishes sample complexity, which measures mistakes or episodes until a near-optimal policy is returned, from regret, which measures reward shortfall against an optimal policy.Source: §1 · p. 1
  • Earlier episodic best-policy identification lower bounds considered deterministic recommendations and stage-independent transitions, while this paper studies stage-dependent transitions and randomized policies.The earlier hard instances consisted of S parallel multi-armed bandit problems; the new lower bound is stated for an MDP with stage-dependent transitions.Source: §1 · pp. 2–3
  • The paper gives a detailed proof of the Ω(√(H^3SAT)) regret lower bound for stage-dependent transitions, previously claimed without a complete proof.The proof uses the same class of hard MDPs as the sample-complexity lower bound and a different construction from the cited sketch.Source: §1 · p. 2
  • The contributions provide unified proofs of sample-complexity and regret lower bounds using one class of hard MDPs and the same information-theoretic tools.The introduction describes the regret proof as matching the earlier claim by Jin et al. (2018).Source: §1 · p. 2

2. Setting and Performance Measures

The paper models episodic MDPs with finite state and action sets, an initial-state distribution, and stage-indexed transitions and rewards. It distinguishes Markov and history-dependent policies and defines algorithms and performance criteria for episodic learning.

2. Setting and Performance Measures

  • An episodic MDP is specified by state and action sets, horizon H, initial distribution, and stage-indexed transition and reward functions, with rewards in [0, 1].The state and action sets are finite.Source: §2 · p. 3
  • A Markov policy selects actions from the current state and stage, whereas a history-dependent policy may condition on the observed history.The paper denotes the corresponding policy classes by ΠMarkov and ΠHist.Source: §2 · p. 3
  • The optimal value is the maximum value over Markov policies, and the paper states that a Markov policy attains it.The value of a Markov policy does not depend on the preceding episode history.Source: §2 · p. 4
  • In best-policy identification, an algorithm interacts through a history-dependent policy, stops at a stopping time, and recommends a Markov policy.The algorithm is represented as (π, τ, bπτ).Source: §2 · p. 4
  • The paper frames episodic reinforcement-learning performance using regret and PAC criteria, including PAC exploration and best-policy identification.For best-policy identification, sample complexity is the number of episodes τ required before stopping.Source: §2 · pp. 4–5

3. Lower Bound Recipe

The lower-bound proofs use a family of hard MDPs and information-theoretic changes of distribution. The construction behaves like a bandit with Θ(HSA) arms and extends to larger state spaces through a tree structure.

3. Lower Bound Recipe

  • The proofs compare nearby hard MDPs with different optimal policies and use changes of distribution to bound expected visits to selected state-action pairs.The information-theoretic tools for these comparisons are gathered separately in Section 3.2.Source: §3 · p. 5

3.1. Hard MDP instances

  • The hard instances behave like bandits with Θ(HSA) arms, with the useful action tied to a particular stage, leaf, and action choice.In the larger-state construction, a waiting state leads to a full A-ary tree whose leaves connect to absorbing good and bad states; one selected leaf-stage-action choice increases the probability of reaching the good state.Source: §3.1 · pp. 5–6

3.2. Change of Distribution Tools

  • The change-of-distribution tools include a KL-divergence definition, a stopped-history identity for MDPs differing in transitions, and a bound on differences in expectations.The stopped-history result applies when the transition distributions satisfy the stated absolute-continuity condition.Source: §3.2 · pp. 7–8

4. Sample Complexity Lower Bounds

The section develops a sample-complexity lower bound for best-policy identification with stage-dependent transitions. Its proof compares a reference MDP with instances that differ at a selected stage, leaf, and action.

4. Sample Complexity Lower Bounds

  • The section gives a minimax lower bound for best-policy identification in MDPs with stage-dependent transitions, using explicit changes of distribution rather than a bandit lower-bound result.The approach also permits best-policy-identification lower bounds for algorithms outputting randomized policies and yields a PAC-MDP lower bound as a corollary.Source: §4 · p. 8
  • Theorem 7 applies under Assumption 1 when ε ≤ H/24, H ≥ 4, and δ ≤ 1/16, and asserts a lower bound for some stage-dependent-transition MDP.The supplied theorem passage does not include the bound's expression.Source: §4 · p. 8
  • The PAC-MDP corollary is stated for algorithms that play deterministic policies in each episode and inherits the assumptions of Theorem 7.The supplied corollary passage does not include its lower-bound expression.Source: §4 · pp. 8–9
  • The proof contrasts a reference MDP with instances altered at one chosen stage, leaf, and action, then relates the algorithm's behavior across those instances.The selected transition change is parameterized by the instance, while the reference MDP has no such optimal action.Source: §4 · p. 9

5. Regret Lower Bound

The section proves a regret lower bound for stage-dependent episodic MDPs using the same hard-instance family and change-of-distribution approach. It compares policy performance across instances with a selected stage, leaf, and action.

5. Regret Lower Bound

  • Theorem 9 asserts that for T ≥ HSA, any algorithm has a stage-dependent-transition MDP on which its regret meets a lower bound.The supplied theorem passage does not include the bound's expression.Source: §5 · p. 11
  • The proof uses a class containing a reference MDP and instances parameterized by a selected stage, leaf, and action, then applies changes of distribution.The construction is described as bandit-like, and the regret argument relates expectations under the altered instances to those under the reference MDP.Source: §5 · pp. 11–12
  • In each altered instance, the optimal policy waits until the selected time to traverse the tree, reach the selected leaf, and take the selected action.That policy is described as attaining the optimal value in the instance.Source: §5 · p. 12

6. Discussion

Theorem 7 and Theorem 9 give lower bounds for MDPs with stage-dependent transitions, with proof adaptations available for stage-independent transitions. The proofs impose a tree-depth condition that limits their scope.

6. Discussion

  • Theorem 7 and Theorem 9 lower bounds hold for MDPs with stage-dependent transitions.Their proofs can be adapted to stage-independent transitions, where the bounds change; the supplied passage does not give the resulting expressions.Source: §6 · p. 14
  • The proofs require a full A-ary tree with roughly S nodes and depth d ≤ H/3.Appendix D describes how to obtain the same bounds when a full tree cannot be built; if d > H/3, the bounds become exponential in H.Source: §6 · p. 14
  • When tree depth d exceeds H/3, the bounds become exponential in H.Source: §6 · p. 14

Appendix A. Change of Distribution: Proof of Lemma 5

The proof invokes almost-sure boundedness and then uses Lemma 13 and the Markov property.

Appendix A. Change of Distribution: Proof of Lemma 5

  • The proof uses that Xt is bounded almost surely.The passage links this to a transition having zero probability.Source: Appendix A · p. 16
  • A transition probability of zero is cited in the boundedness argument.Source: Appendix A · p. 16
  • The proof then invokes Lemma 13 and the Markov property.Source: Appendix A · p. 16

Appendix B. PAC-MDP Lower Bound: Proof of Corollary 8

The proof converts a PAC-MDP algorithm into a best-policy-identification algorithm by fixing its stopping time and recommending its most-played deterministic policy. The argument relates an incorrect recommendation to exceeding the PAC mistake bound.

Appendix B. PAC-MDP Lower Bound: Proof of Corollary 8

  • The constructed BPI algorithm stops deterministically at τ = 2T(ε, δ) + 1 and recommends the most-played deterministic policy.Its sampling rule is that of the original algorithm.Source: Appendix B · p. 17
  • In the constructed MDPs, every non-optimal deterministic policy is more than ε worse than the unique optimal policy.The passage gives a reward difference of 2ε.Source: Appendix B · p. 17
  • The proof states that ε would be larger than T(ε, δ), then says the defined BPI algorithm satisfies a condition that the cited passage does not specify.Source: Appendix B · p. 17

Appendix C. Recovering the lower bounds for stage-independent transitions

The appendix adapts the lower-bound proofs to stage-independent transitions and discusses relaxing a tree-structure assumption. The adaptation removes the waiting state and makes rewards stage-independent.

Appendix C. Recovering the lower bounds for stage-independent transitions

  • For stage-independent transitions, the proofs remove the waiting state and start the agent at sroot, roughly corresponding to setting H = 1.Source: Appendix C · p. 17
  • The stage-independent adaptation also uses rewards that do not depend on h.Source: Appendix C · p. 17

Appendix D. Relaxing Assumption 1

  • Assumption 1 requires S = 3 + (A^d − 1)/(A − 1) for an integer d.This is one stated condition of the assumption used in the proofs.Source: Appendix D · p. 18

D.1. Relaxing (i)

The construction relaxes the tree-size assumption by balancing an A-ary tree and handling leaves that would otherwise be at different depths. When the horizon is too short to traverse the tree, a smaller state subset is used.

D.1. Relaxing (i)

  • A balanced tree is built from half the available states, then extra child states bring leaves at depth d −2 to depth d −1.Any remaining states other than sw, sg, or sb can be merged into absorbing states sg or sb.Source: §D.1 · p. 18
  • At least (S −3)/8 leaves suffice to preserve lower bounds of the same order in Theorems 7 and 9.The construction's leaf count is bounded above by S and below by (S −3)/8.Source: §D.1 · p. 18

D.2. Relaxing (ii)

  • The horizon condition H ≥3d ensures the agent can traverse the tree to the rewarding state; when it fails, the construction uses a smaller state subset.The depth satisfies d = logA S + c for a constant c ∈[−1, 2].Source: §D.2 · p. 18

D.3. Lower bounds

The section states BPI, PAC-MDP, and regret lower bounds without Assumption 1. Its theorem statements specify settings and eligibility conditions, while the appendix includes a tree-leaf bound used in the construction.

D.3. Lower bounds

  • The arguments yield BPI, PAC-MDP, and regret lower bounds without requiring Assumption 1.Corollary 11 concerns deterministic policies in each episode; Theorem 12 concerns stage-dependent transitions and T ≥HSA.Source: §D.3 · p. 19
  • Theorem 10 gives a BPI lower bound for stage-dependent transitions when S ≥11, A ≥4, H ≥6, ε ≤H/24, and δ ≤1/16.The theorem applies to an (ε, δ)-PAC algorithm for best policy identification in any finite episodic MDP.Source: §D.3 · p. 19

Appendix E. Technical Lemmas

  • For a balanced A-ary tree, Lemma 16 states that the number of leaves L is at least S/4.Source: Appendix E · p. 20
Loading 2010.03531v1…