Metraipolis › archive › dc_307a108bfeff

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

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.40165
License (as archived): CC0-1.0
Archived: 2026-11-01T02:25:22.978Z
SHA-256 of the archived text: 809560f7deb67404723f42dde98b23a38795a4e601b9a232b258b6883fee113e
Stable URL of this page: https://metraipolis.com/documento/dc_307a108bfeff

How to cite

Closing the Log Gap: Minimax-Optimal Regret for Episodic RL — arXiv:2610.40165 — arXiv (en), https://arxiv.org/abs/2610.40165 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_307a108bfeff (Metraipolis archive dc_307a108bfeff, sha256 809560f7deb67404723f42dde98b23a38795a4e601b9a232b258b6883fee113e)

BibTeX

@misc{dc307a108bfeff,
  title = {Closing the Log Gap: Minimax-Optimal Regret for Episodic RL — arXiv:2610.40165},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40165},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_307a108bfeff; sha256 809560f7deb67404723f42dde98b23a38795a4e601b9a232b258b6883fee113e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40165. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.40165 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:12:44.204Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).