betaFeedback

WorksComputer Science

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

Abstract

In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as H3SAK\sqrt{H^3 S A K} for sufficiently large KK, where HH is the episode length, KK is the number of episodes, and SS and AA are the numbers of states and actions, respectively. Our method is the first to match the minimax lower bound 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, δ)-PAC best-policy identification, which is the first to match the Ω(H3SAlog⁡(1δ)ε−2)Ω\big(H^3 SA\log(\frac{1}δ)\varepsilon^{-2}\big) minimax lower bound up to constants in some regimes.

Paper details

vlnc:W_7cr7p9ka
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…