Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds

DOI10.1287/MOOR.2022.1266MaRDI QIDQ6199245zbMATH OpenOpenAlexFDO

Authors Shipra Agrawal, Randy Jia

Publication date 23 February 2024

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.07041

zbMATH Keywords

Markov decision process regret boundsreinforcement learningThompson sampling

Mathematics Subject Classification ID

General topics in artificial intelligence (68T01) Markov and semi-Markov decision processes (90C40)

Abstract: We present an algorithm based on posterior sampling (aka Thompson sampling) that achieves near-optimal worst-case regret bounds when the underlying Markov Decision Process (MDP) is communicating with a finite, though unknown, diameter. Our main result is a high probability regret upper bound of $ildeO(DSsqrtAT)$ for any communicating MDP with $S$ states, $A$ actions and diameter $D$. Here, regret compares the total reward achieved by the algorithm to the total expected reward of an optimal infinite-horizon undiscounted average reward policy, in time horizon $T$. This result closely matches the known lower bound of $Omega(sqrtDSAT)$. Our techniques involve proving some novel results about the anti-concentration of Dirichlet distribution, which may be of independent interest.

Recommendations

• Near-optimal regret bounds for reinforcement learning
• Regret bounds for reinforcement learning via Markov chain concentration
• Learning to optimize via posterior sampling
• Near-optimal PAC bounds for discounted MDPs
• Near-optimal regret bounds for Thompson sampling

This page was built for publication: Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199245)