---
title: "Convergence of Reinforcement Learning with General Function Approximators"
authors:
  - "Vassilis A. Papavassiliou"
  - "Stuart J. Russell"
doi: ""
url: "https://ijcai.org/proceedings/1999/107"
pdf: "https://ijcai.org/proceedings/1999/0107.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "748-756"
track: "Machine Learning"
keywords:
---

# Convergence of Reinforcement Learning with General Function Approximators

Vassilis A. Papavassiliou, Stuart J. Russell

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, 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.