REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

Peter Bartlett, Ambuj Tewari
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:27-34, 2009.

Abstract

We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of  O(HSpAT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-bartlett09a, title = {{REGAL}: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs}, author = {Bartlett, Peter and Tewari, Ambuj}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {27--34}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/bartlett09a/bartlett09a.pdf}, url = {https://proceedings.mlr.press/r7/bartlett09a.html}, abstract = {We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of  O(HSpAT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs %A Peter Bartlett %A Ambuj Tewari %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-bartlett09a %I PMLR %P 27--34 %U https://proceedings.mlr.press/r7/bartlett09a.html %V R7 %X We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of  O(HSpAT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds. %Z Reissued by PMLR on 04 October 2026.
APA
Bartlett, P. & Tewari, A.. (2009). REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:27-34 Available from https://proceedings.mlr.press/r7/bartlett09a.html. Reissued by PMLR on 04 October 2026.

Related Material