Convergence of Reinforcement Learning with General Function Approximators

Papavassiliou, Vassilis A.; Russell, Stuart J.

Convergence of Reinforcement Learning with General Function Approximators

Vassilis A. Papavassiliou, Stuart J. Russell

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Machine Learning. Pages 748-756.

Abstract

A key open problem in reinforcement learning is to assure convergence when using a compact hypothesis class to approximate the value function. Although the standard temporal-difference learning algorithm has been shown to converge when the hypothesis class is a linear combination of fixed basis functions, it may diverge with a general (nonlinear) hypothesis class. This paper describes the Bridge algorithm, a new method for reinforcement learning, and shows that it converges to an approximate global optimum for any agnostically learnable hypothesis class. Convergence is demonstrated on a simple example for which temporal-difference learning fails. Weak conditions are identified under which the Bridge algorithm converges for any hypothesis class. Finally, connections are made between the complexity of reinforcement learning and the PAC-learnability of the hypothesis class.

Vassilis A. Papavassiliou, and Stuart J. Russell. 1999. Convergence of Reinforcement Learning with General Function Approximators. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99. IJCAI, 748–756. https://ijcai.org/proceedings/1999/107

@inproceedings{ijcai1999p107,
  title     = {Convergence of Reinforcement Learning with General Function Approximators},
  author    = {Papavassiliou, Vassilis A. and Russell, Stuart J.},
  booktitle = {Proceedings of the Sixteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-99}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Thomas Dean},
  pages     = {748--756},
  year      = {1999},
  note      = {Machine Learning},
  url       = {https://ijcai.org/proceedings/1999/107},
}

TY  - CPAPER
TI  - Convergence of Reinforcement Learning with General Function Approximators
AU  - Papavassiliou, Vassilis A.
AU  - Russell, Stuart J.
T2  - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1999
SP  - 748
EP  - 756
UR  - https://ijcai.org/proceedings/1999/107
ER  -