Reproduce “Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Runlong Zhou, Zihan Zhang, Maryam Fazel, Simon S. Du

This research introduces an algorithm for finite-horizon tabular Markov Decision Processes that achieves an asymptotically optimal regret bound of O(√(SAK)), completely eliminating dependence on the planning horizon H. The method establishes that, up to poly-logarithmic factors, these MDPs are statistically as difficult as contextual bandits in terms of regret.

Key insights

  • The monotonicity of optimal value functions in time-homogeneous MDPs with non-negative rewards allows for their effective discretization, reducing complexity from H-dependent to H-independent.
  • Precise control of cumulative clipped variance, achieved through a novel total-deviation bound, is crucial for obtaining asymptotically optimal regret rates that are independent of the horizon.
  • Combining horizon truncation with a reward-aware exploration strategy enables efficient learning by focusing planning on a shorter horizon while reserving a suffix for targeted exploration without significant value loss.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.