PaperlayerView exact revision on arXiv

Source-linked AI summary

Closing the Log Gap: Minimax-Optimal Regret for Episodic RL

Guy Zamir, Victor Boone, Matthew Zurek, Yudong Chen

arXiv:2610.40165v1cs.LGstat.ML

TL;DR

Episodic tabular RL has a minimax-regret gap: previous guarantees retained extra logarithmic factors. The paper introduces a MOSS-style UCBVI variant and an analysis that handles under-optimism. It reports matching the minimax regret lower bound without extra polylogarithmic factors and derives a PAC best-policy result matching its lower bound in some regimes.

  • Problem

    Prior episodic-RL regret guarantees retained extra polylogarithmic factors in the leading term, leaving the true minimax rate unattained.

    Source: §1 · p. 1

  • Method

    MORE-UCBVI uses MOSS-style bonuses adapted to visit counts and variance estimates, and analyzes the propagation of under-optimism.

    Source: §5 · p. 7, §7.2 · p. 10

  • Results

    The paper reports matching the minimax regret lower bound without extra polylogarithmic factors for sufficiently large K.

    Source: §1 · p. 2, §8 · p. 12

  • Takeaways & Limitations

    The paper also gives a PAC best-policy identification algorithm matching the minimax sample-complexity lower bound in some regimes.

    Source: §1 · p. 2

    The setting assumes the learner knows the state and action spaces, horizon, reward functions, and number of episodes, but not the transition kernels or initial-state distribution.

    Source: §2 · p. 3

Abstract

from arXiv · show

In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as $\sqrt{H^3 S A K}$ for sufficiently large $K$, where $H$ is the episode length, $K$ is the number of episodes, and $S$ and $A$ are the numbers of states and actions, respectively. Our method is the first to match the minimax lower bound \emph{without extra polylog factors}. We introduce a variant of UCBVI which does not maintain strictly optimistic estimates, and uses MOSS-style exploration bonuses whose logarithmic terms adapt to both visit counts and estimated variances. A key challenge is controlling the propagation of errors caused by under-optimism, which we accomplish in an occupancy-weighted way, avoiding logarithmic overhead that would be incurred by uniform-over-rows concentration. Our analysis develops time-uniform and variance-aware concentration bounds that may be of independent interest. As a corollary we also develop an algorithm for $(\varepsilon, \delta)$-PAC best-policy identification, which is the first to match the $\Omega\big(H^3 SA\log(\frac{1}{\delta})\varepsilon^{-2}\big)$ minimax lower bound up to constants in some regimes.

1 Introduction

The paper closes the gap between prior episodic-RL regret guarantees and the minimax rate without extra logarithmic factors. It does so with a MOSS-style UCBVI variant and an analysis designed to handle estimates that can be under-optimistic.

1 Introduction

  • Prior expected-regret guarantees hid polylogarithmic factors, so no earlier algorithm attained the true minimax rate.The paper identifies the gap as applying to the leading regret term.Source: §1 · p. 1
  • MORE-UCBVI replaces UCB-style bonuses with MOSS-style bonuses whose logarithmic terms adapt to visit counts and estimated variances, while allowing under-optimism.Its value estimates may underestimate the optimal value function.Source: §1 · p. 2
  • A stability argument tracks how under-optimism propagates through Bellman updates, bounding its cumulative cost without union-bound logarithmic overhead.This replaces the standard monotonicity-based optimism induction.Source: §1 · p. 2
  • The paper also presents a time-uniform Bernstein inequality and a PAC best-policy algorithm matching the sample-complexity lower bound in some regimes.The PAC lower bound is attributed to Domingues et al. [2021].Source: §1 · p. 2
  • Related algorithms target other goals: MVP improves horizon dependence, EQO+ gives guarantees across confidence levels, and UCBMQ offers cheaper memory, while these constructions incur logarithmic factors.The passage describes MVP [Zhang et al., 2021], EQO+ [Lee and Oh, 2025, 2026], and UCBMQ [Ménard et al., 2021].Source: §1 · pp. 2–3

2 Preliminaries

The preliminaries define the tabular episodic MDP setting and the learner’s minimax-regret objective. They also establish notation for transition rows, value functions, and common shorthand.

2 Preliminaries

  • A tabular episodic MDP has finite state and action spaces, horizon H, step-dependent transition kernels and deterministic rewards, and an initial-state distribution.The learner knows the rewards and problem dimensions but not the transition kernels or initial distribution.Source: §2 · p. 3
  • The learner acts over K episodes without knowing transitions or the initial distribution, and the objective is expected regret uniformly over MDPs with the specified dimensions.This is the paper’s worst-case, or minimax, regret objective.Source: §2 · p. 3

2.1 Additional Notation

  • For a state-action pair at step h, P_h,s,a denotes its transition-probability row; multiplying it by a value vector gives the expected next-state value.The notation also uses [n] for {1, …, n}, x+ for max{0, x}, and log≥0(x) for log(max{1, x}).Source: §2.1 · p. 3

3 Insufficiency of State-of-the-Art Methods

The section argues that existing UCBVI-style methods incur logarithmic factors because their fixed-log bonuses are too large for a minimax regret bound. It introduces this as the obstacle motivating a different bonus design.

3 Insufficiency of State-of-the-Art Methods

  • Existing approaches to the minimax rate still incur polylogarithmic factors, and the paper identifies optimistic bonus design as the culprit.The section focuses on a UCBVI variant as its algorithmic route.Source: §3 · p. 4

3.1 The UCBVI Algorithm

  • UCBVI performs dynamic programming with an overestimated reward and then acts greedily with respect to its computed action values.The estimates use empirical visit counts gathered before each episode.Source: §3.1 · p. 4

3.2 Why log(K) Appears in Variants of UCBVI

  • Converting high-probability bounds to expectation uses a confidence level that controls the worst-case regret when the good event fails, contributing logarithmic dependence on K.The displayed equations are incomplete in the supplied text, so no sharper bound is reported here.Source: §3.2 · pp. 4–5
  • The standard bonus analysis carries a fixed logarithmic factor into the regret bound, preventing these bonuses from attaining the minimax rate.The section states that this is not merely an artifact of the analysis: fixed-log bonuses are too large, with supporting lower bounds for UCB in bandits.Source: §3.2 · p. 5

4 Variance-Aware Time-Uniform Concentration

This section introduces time-uniform, variance-aware concentration as a way to remove the fixed logarithmic factor associated with standard UCBVI bonuses. The bound supports smaller bonuses even when estimates are not guaranteed to remain optimistic.

4 Variance-Aware Time-Uniform Concentration

  • The section’s concentration tool addresses the fixed logarithmic factor identified in standard UCBVI bonuses.That factor is described as an obstacle to minimax optimality.Source: §4 · p. 5
  • MOSS-style bonuses make logarithmic terms shrink as observations accumulate, allowing the factor associated with fixed-log bonuses to become removable.The log term depends on visit counts rather than remaining static.Source: §4 · p. 5
  • The resulting smaller bonuses need not preserve optimism, so the analysis instead controls how far estimates can fall below the true value.The passage connects this control to variance-aware, time-uniform concentration.Source: §4 · p. 6
  • Theorem 4.1 bounds the probability that an empirical mean plus a confidence interval underestimates the true mean by at least Δ at any sample size.This time-uniform Bernstein analogue applies without a union bound over sample sizes.Source: §4 · p. 6

5 Our Algorithm: MORE-UCBVI

MORE-UCBVI retains the UCBVI framework but changes its exploration bonus. Its MOSS-style and UCB-style components balance expected-regret control with high-probability guarantees.

5 Our Algorithm: MORE-UCBVI

  • MORE-UCBVI follows UCBVI’s empirical-kernel value iteration and acts greedily with respect to the resulting Q estimates.The transition kernel is updated before each episode; the policy then acts greedily for that episode.Source: §5 · pp. 6–7
  • Its bonus is the difference from original UCBVI, combining a MOSS-style component for large visit counts with a UCB-style component for small counts.The bonus is the maximum of b1 and b2; b1 dominates for large n, while b2 reflects the sub-exponential tail at small n.Source: §5 · pp. 6–7
  • The logarithmic factor in b1 adapts to visit count and estimated variance, and B = HK/(SA) sets the exploration budget.As visits increase, the logarithmic factor decreases to 1; larger B increases bonuses, while smaller B worsens under-optimism.Source: §5 · pp. 6–7

6 Main Theorem

Theorem 6.1 establishes a leading regret bound matching the minimax lower bound up to a universal constant, without extra logarithmic factors. The paper also derives a best-policy identification guarantee in a specified parameter regime.

6 Main Theorem

  • Theorem 6.1 gives a leading regret term matching the minimax lower bound for time-inhomogeneous episodic MDPs up to a universal constant, without extra logarithmic factors.The stated gap closure holds when K is greater than a polynomial of H, S, and A.Source: §6 · p. 7
  • The stated best-policy identification regime requires ε ≤ 1/(S(log(eHSA))^2) and δ ≥ exp(−SAH).The passage identifies this as the regime in which ε is sufficiently small and δ is not exponentially small in SAH.Source: §6 · p. 8
  • Theorem 6.1 yields an algorithm for (ε, δ)-PAC best-policy identification by regret-to-PAC conversion and repeated policy evaluation.The described conversion runs for K0 episodes, samples policies, and repeats O(log(1/δ)) times before returning the best evaluated policy.Source: §6 · p. 8

7 Proof Sketch

The proof sketch balances under-optimism against over-optimism to control regret without logarithmic overhead. It replaces strict optimism arguments with stability and sharper concentration and bonus-summation techniques.

7 Proof Sketch

  • The regret decomposition separates under-optimism, which grows as bonuses shrink, from over-optimism, which grows as bonuses increase.The proof seeks to balance these two costs; with MOSS-style bonuses, the under-optimism term need not vanish.Source: §7 · p. 8

7.1 Bounding T −: Under-Optimism

  • For under-optimism, Bellman-update stability controls how a next-step shortfall propagates when smaller bonuses no longer guarantee simultaneous optimism.Unlike the standard monotonicity-based induction, this argument permits unordered next-step estimates while bounding the additional cost.Source: §7.1 · p. 9
  • Weighting shortfalls by true-MDP occupancies under π⋆ makes fixed-(h, s, a) expected bounds sufficient, avoiding simultaneous concentration over all rows.The occupancies are deterministic; using empirical-kernel occupancies instead would create data-dependence issues.Source: §7.1 · p. 10
  • Time-uniform concentration bounds adapt to the visit counts chosen during learning, avoiding a union bound over possible counts.The analysis integrates the tail bound because n_h^k(s, a) is selected adaptively.Source: §7.1 · p. 10

7.2 Bounding T +: Over-Optimism

  • For over-optimism, concentration directly on sums of deviations avoids the logarithmic cost of controlling every visit count simultaneously.The MOSS bonus’s logarithmic term decreases with visits and variance; summing these terms directly avoids extracting a √log B factor.Source: §7.2 · pp. 11–12

8 Conclusion

The paper closes the episodic-RL regret gap by matching the minimax lower bound without extra polylogarithmic factors. The appendix proof handles under-optimism through bonus stability and occupancy-weighted shortfalls, then decomposes the remaining over-optimism cost.

8 Conclusion

  • The conclusion reports a match to the minimax regret lower bound without extra polylogarithmic factors, using a MOSS-style bonus incorporating visit counts and variance estimates.The authors identify improving the additive burn-in regret term and handling the time-homogeneous setting as future directions.Source: §8 · p. 12

A.2 Regret Decomposition

  • Regret is decomposed into under-optimism and over-optimism costs, which are bounded separately.The proof interprets T− as the cost of under-optimism and T+ as the cost of over-optimism.Source: §A.2 · p. 17

A.3 High Probability Good Event

  • A high-probability event holds with probability at least 1 − 1/K^3 and supplies simultaneous inequalities for all state-action-stage rows, sample sizes, and eligible value functions.The event is established using Bernstein’s inequality and a union bound over rows, next states, and sample sizes.Source: §A.3 · p. 17

A.4.1 Stability Properties of Our Bonus Function

  • The bonus is stable as the value function increases, yielding a monotone Bellman update and a stability guarantee even for unordered value functions.For ordered V ≤ V′, the bonus increase is bounded by (1/(16H))p(V′ − V); the general comparison is stated for arbitrary V and V′.Source: §A.4.1 · pp. 17–18

A.4.2 Proof of Lemma A.3

  • Under-optimism is controlled by weighting shortfalls with true-MDP visitation probabilities, so the proof does not require a union bound making every shortfall vanish simultaneously.A time-uniform concentration inequality is used to bound expected shortfall at a fixed state-action-stage tuple.Source: §A.4.2 · p. 19

A.5 Bounding T +: Expected Amount of Over-optimism

  • The over-optimism cost is further split into transition-estimation errors applied to the optimal value and value-function difference, plus bonuses along the learner’s trajectory.The proof also tracks two variance sums for that trajectory.Source: §A.5 · pp. 20–21

A.5.1 A Few Useful Technical Results

This subsection collects variance-sum and deterministic-sum bounds used in the over-optimism analysis.

A.5.1 A Few Useful Technical Results

  • A.9 bounds the sum of optimal-value variances using the total visit counts, and the subsection also gives a bound for the corresponding floored variances.The displayed bound values are not stated in the supplied passages.Source: §A.5.1 · p. 21
  • The variance bounds are organized around total visits to each stage-state-action tuple rather than only the learner’s current counts.The total visit counts are denoted Nh(s, a).Source: §A.5.1 · p. 21
  • A.10 supplies a deterministic sum bound for use in the later analysis.The passage identifies the lemma and says its proof is in Appendix B.6, but does not state the bound’s value.Source: §A.5.1 · p. 21

A.5.2 Analysis of T +

The proof bounds over-optimism by controlling transition errors and summing the variance-aware bonus, then combines this with the under-optimism bound to establish the expected-regret result.

A.5.2 Analysis of T +

  • A general concentration inequality for sums of deviations with slackness is developed as a tool for bounding the first over-optimism term.The authors distinguish it from time-uniform Bernstein-type concentration, which controls a maximum over deviations.Source: §A.5.2 · p. 21

A.5.3 Analysis of T +

  • The analysis bounds transition error applied to the value-function difference using a term involving E[Vardiff] and an additional lower-order term.The good event is used to relate empirical and true transition variances.Source: §A.5.3 · p. 22, §A.5.4 · p. 24

A.5.4 Analysis of T +

  • A variance-normalized MOSS-sum lemma lets the bonus contributions be summed without introducing log factors.The analysis approximates empirical variances by true variances up to an additive lower-order term before splitting the value function into optimal-value and difference components.Source: §A.5.4 · pp. 23–24

A.5.5 Conclusion: Bounding T + and Proving Lemma A.8

  • The proof relates the accumulated variance of value-function differences to both over-optimism and under-optimism costs.The stated relation is E[Vardiff] ≤ 4H E[T+] + 2H E[T−].Source: §A.5.5 · p. 24

A.6 Conclusion: Bounding the Expected Regret and Proving Theorem 6.1

  • The proof concludes by combining the regret decomposition with bounds on both under-optimism and over-optimism to establish Theorem 6.1’s expected-regret result.The supplied passage does not include the resulting bound’s full expression.Source: §A.6 · p. 24

B.1 Proof of Regret Decomposition, Lemma A.1

  • The regret decomposition proof identifies the first sum as T− and bounds the expected second sum by E[T+].The argument is carried out for each episode before summing over episodes.Source: §B.1 · pp. 25–26

B.2 Proof of Probability of the Good Event E, Lemma A.2

  • The cited proof step uses a union bound for (°1), and for (°2) bounds the summand via Bernstein’s inequality (Lemma B.1) and the number of terms by HS2AK.Source: §B.2 · p. 26

B.3 Proof of Ordered Stability, Lemma A.4

  • For V and V′, the second branch in b2 is the same; taking the maximum with this common term cannot increase the numerator difference, and both denominators are at least b2(p, n, V).Source: §B.3 · p. 28

B.4 Proof of Expected Shortfall, Lemma A.7

These appendix proofs support the expected-shortfall and variance bounds used in the regret analysis, including a concentration argument that handles random visit counts.

B.4 Proof of Expected Shortfall, Lemma A.7

  • Time-uniform concentration applies at a random visit count without conditioning on that count or on the good event, enabling the expected-shortfall bound.The observations for a fixed state-action-stage tuple are treated as an i.i.d. sequence, with centered values bounded by H.Source: §B.4 · p. 30

B.5 Proof of the Variance Sum Bound, Lemma A.9

  • The variance-sum proof uses the Bellman gap and telescoping across episodes and stages to obtain its bound.The proof notes that the Bellman gap is nonnegative and that rewards are bounded by 1.Source: §B.5 · pp. 30–31

B.7 Proof of the Concentration Result on Sums with Slackness, Proposition A.12

  • The concentration proof handles low visit counts with Jensen’s inequality and high visit counts with Bernstein’s inequality.The two regimes are separated at a visit-count threshold because Bernstein tails alone are not tight enough at low counts.Source: §B.7 · p. 32

3 Bound, Lemma A.16

  • The bonus-sum bound splits variance terms into optimal-value and value-difference components, then uses the MOSS-style sum bound for one contribution.The remaining terms are bounded using Cauchy–Schwarz and a deterministic sum bound.Source: §3 · pp. 33–34

B.9 Proof of the Vardiff Bound

  • The Vardiff proof writes the value-function difference stage by stage and sums over episodes to connect it to T− and T+.The supplied passage states that the desired result follows from these sums and the definitions of the two costs.Source: §B.9 · pp. 34–35

C Proof of Theorem 4.1

The proof of Theorem 4.1 uses a geometric grid and maximal Bernstein bounds, with a super-additive, increasing function to control the resulting terms. The related-work discussion notes that existing best-policy identification guarantees retain logarithmic gaps from the minimax lower bound.

C Proof of Theorem 4.1

  • The function ϕ is increasing and super-additive on its nonnegative domain, properties used in the proof’s concentration argument.The proof verifies these properties by its derivative and an explicit super-additivity expression.Source: C Proof of Theorem 4.1 · p. 36
  • A geometric grid, maximal Bernstein inequality, and super-additivity of ϕℓ are used to bound the event probability in the proof.The proof also treats zero variance as a trivial case and applies the maximal Bernstein inequality on each grid level.Source: C Proof of Theorem 4.1 · pp. 36–37

D.1 Related Work

  • Existing best-policy identification guarantees still have multiplicative logarithmic gaps from the minimax lower bound.The cited lower bound assumes H ≥ Ω(log A S) and sufficiently large S, A, and H/ε; it allows random stopping times and concerns expected stopping time.Source: §D.1 · p. 37
  • Prior regret-to-PAC conversions can retain suboptimal logarithmic factors, while Zhang et al. [2025] is noted to avoid additive burn-in regret despite logarithmic factors in its leading regret term.The discussion says that, to the authors’ knowledge, prior work still has suboptimal logarithmic factors even when 1/δ = O(1).Source: §D.1 · p. 38

D.2 Algorithm and Proof of Corollary 6.2

Algorithm 2 generates candidate policies by sampling a uniformly random episode from independent runs of Algorithm 1, then estimates their values and selects the best. Repeating this process and estimating candidate values amplifies the chance of returning an ε-optimal policy.

D.2 Algorithm and Proof of Corollary 6.2

  • Algorithm 2 generates each candidate from a uniformly sampled episode among K0 episodes of Algorithm 1, yielding an ε/3-optimal candidate with constant probability.K0 is chosen so the expected average regret is at most ε/6.Source: §D.2 · p. 38
  • m = O(log2(2/δ)) candidate policies are independently generated, evaluated over M episodes, and the estimated-best policy is returned.The stated amplification argument selects the estimated best among candidates.Source: §D.2 · pp. 38, 40
  • For K ≥ C4H3S3A(log(eHSA))4, the proof conditions ensure the leading regret term dominates the additive term.The regret expression is C1H3SAK + C2H3S2A(log(K))2.Source: §D.2 · p. 39
  • The combined good events have probability at least 1 − δ, supporting the stated confidence guarantee for the policy-selection procedure.The proof bounds candidate suboptimality and value-estimation error before combining the events.Source: §D.2 · p. 40
Loading 2610.40165v1…