Exploring compact reinforcement-learning representations with linear regression

Thomas Walsh, Istvan Szita, Carlos Diuk, Michael Littman
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:591-598, 2009.

Abstract

This paper presents a new algorithm for online linear regression whose efficiency guarantees satisfy the requirements of the KWIK (Knows What It Knows) framework. The algorithm improves on the computational and storage complexity bounds of the current state-of-the-art procedure in this setting. We explore several applications of this algorithm for learning compact reinforcement-learning representations. We show that KWIK linear regression can be used to learn the reward function of a factored MDP and the probabilities of action outcomes in Stochastic STRIPS and Object Oriented MDPs, none of which have been proven to be efficiently learnable in the RL setting before. We also combine KWIK linear regression with other KWIK learners to learn larger portions of these models, including experiments on learning factored MDP transition and reward functions together.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-walsh09a, title = {Exploring compact reinforcement-learning representations with linear regression}, author = {Walsh, Thomas and Szita, Istvan and Diuk, Carlos and Littman, Michael}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {591--598}, 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/walsh09a/walsh09a.pdf}, url = {https://proceedings.mlr.press/r7/walsh09a.html}, abstract = {This paper presents a new algorithm for online linear regression whose efficiency guarantees satisfy the requirements of the KWIK (Knows What It Knows) framework. The algorithm improves on the computational and storage complexity bounds of the current state-of-the-art procedure in this setting. We explore several applications of this algorithm for learning compact reinforcement-learning representations. We show that KWIK linear regression can be used to learn the reward function of a factored MDP and the probabilities of action outcomes in Stochastic STRIPS and Object Oriented MDPs, none of which have been proven to be efficiently learnable in the RL setting before. We also combine KWIK linear regression with other KWIK learners to learn larger portions of these models, including experiments on learning factored MDP transition and reward functions together.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Exploring compact reinforcement-learning representations with linear regression %A Thomas Walsh %A Istvan Szita %A Carlos Diuk %A Michael Littman %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-walsh09a %I PMLR %P 591--598 %U https://proceedings.mlr.press/r7/walsh09a.html %V R7 %X This paper presents a new algorithm for online linear regression whose efficiency guarantees satisfy the requirements of the KWIK (Knows What It Knows) framework. The algorithm improves on the computational and storage complexity bounds of the current state-of-the-art procedure in this setting. We explore several applications of this algorithm for learning compact reinforcement-learning representations. We show that KWIK linear regression can be used to learn the reward function of a factored MDP and the probabilities of action outcomes in Stochastic STRIPS and Object Oriented MDPs, none of which have been proven to be efficiently learnable in the RL setting before. We also combine KWIK linear regression with other KWIK learners to learn larger portions of these models, including experiments on learning factored MDP transition and reward functions together. %Z Reissued by PMLR on 04 October 2026.
APA
Walsh, T., Szita, I., Diuk, C. & Littman, M.. (2009). Exploring compact reinforcement-learning representations with linear regression. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:591-598 Available from https://proceedings.mlr.press/r7/walsh09a.html. Reissued by PMLR on 04 October 2026.

Related Material