Convergence of reinforcement learning with general function approximators

A key open problem in reinforcement learning is to assure convergence when using a compact hy-pothesis class to approximate the value function. Although the standard temporal-difference learning algorithm has been shown to converge when the hy-pothesis class is a linear combination of fixed ba-sis functions, it may diverge with a general (non-linear) hypothesis class. This paper describes the Bridge algorithm, a new method for reinforcement learning, and shows that it converges to an approxi-mate 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 un-der which the Bridge algorithm converges for any hypothesis class. Finally, connections are made be-tween the complexity of reinforcement learning and the PAC-learnability of the hypothesis class.