A PAC RL Algorithm for Episodic POMDPs

Zhaohan Daniel Guo, Shayan Doroudi, Emma Brunskill
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:510-518, 2016.

Abstract

Many interesting real world domains involve reinforcement learning (RL) in partially observable environments. Efficient learning in such domains is important, but existing sample complexity bounds for partially observable RL are at least exponential in the episode length. We give, to our knowledge, the first partially observable RL algorithm with a polynomial bound on the number of episodes on which the algorithm may not achieve near-optimal performance. Our algorithm is suitable for an important class of episodic POMDPs. Our approach builds on recent advances in the method of moments for latent variable model estimation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-guo16b, title = {A PAC RL Algorithm for Episodic POMDPs}, author = {Guo, Zhaohan Daniel and Doroudi, Shayan and Brunskill, Emma}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {510--518}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/guo16b.pdf}, url = {https://proceedings.mlr.press/v51/guo16b.html}, abstract = {Many interesting real world domains involve reinforcement learning (RL) in partially observable environments. Efficient learning in such domains is important, but existing sample complexity bounds for partially observable RL are at least exponential in the episode length. We give, to our knowledge, the first partially observable RL algorithm with a polynomial bound on the number of episodes on which the algorithm may not achieve near-optimal performance. Our algorithm is suitable for an important class of episodic POMDPs. Our approach builds on recent advances in the method of moments for latent variable model estimation.} }
Endnote
%0 Conference Paper %T A PAC RL Algorithm for Episodic POMDPs %A Zhaohan Daniel Guo %A Shayan Doroudi %A Emma Brunskill %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-guo16b %I PMLR %P 510--518 %U https://proceedings.mlr.press/v51/guo16b.html %V 51 %X Many interesting real world domains involve reinforcement learning (RL) in partially observable environments. Efficient learning in such domains is important, but existing sample complexity bounds for partially observable RL are at least exponential in the episode length. We give, to our knowledge, the first partially observable RL algorithm with a polynomial bound on the number of episodes on which the algorithm may not achieve near-optimal performance. Our algorithm is suitable for an important class of episodic POMDPs. Our approach builds on recent advances in the method of moments for latent variable model estimation.
RIS
TY - CPAPER TI - A PAC RL Algorithm for Episodic POMDPs AU - Zhaohan Daniel Guo AU - Shayan Doroudi AU - Emma Brunskill BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-guo16b PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 510 EP - 518 L1 - http://proceedings.mlr.press/v51/guo16b.pdf UR - https://proceedings.mlr.press/v51/guo16b.html AB - Many interesting real world domains involve reinforcement learning (RL) in partially observable environments. Efficient learning in such domains is important, but existing sample complexity bounds for partially observable RL are at least exponential in the episode length. We give, to our knowledge, the first partially observable RL algorithm with a polynomial bound on the number of episodes on which the algorithm may not achieve near-optimal performance. Our algorithm is suitable for an important class of episodic POMDPs. Our approach builds on recent advances in the method of moments for latent variable model estimation. ER -
APA
Guo, Z.D., Doroudi, S. & Brunskill, E.. (2016). A PAC RL Algorithm for Episodic POMDPs. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:510-518 Available from https://proceedings.mlr.press/v51/guo16b.html.

Related Material