Reproduce “Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation” 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
Pihe Hu, Yu Chen, Longbo Huang
Researchers from Tsinghua University developed LSVI-UCB`, an algorithm for episodic linear Markov Decision Processes, which achieves a nearly minimax optimal regret bound of O(Hdsqrt(T)). This work closes a sqrt(Hd) statistical gap compared to prior approaches and matches the theoretical lower bound.
Key insights
- A novel Bernstein self-normalized bound for vector-valued martingales was introduced, precisely accounting for the attenuation of martingale differences and leading to a tighter exploration radius.
- The principle of "conservatism of elliptical potentials" enables adaptive and precise control over variance estimates and exploration bonuses, ensuring the main term of the bonus remains small.
- A refined analysis of the deviation term, separating it into a dominant part and a correction term, eliminates an extra sqrt(d) dependency previously introduced by covering net arguments.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.