PaperBank

	Reinforcement Learning and Artificial Intelligence (RLAI
	J. A. Boyan and A. W. Moore. Generalization in reinforcement learning: safely approximating the value function. In Advances in Neural Information Processing Systems, San Mateo, CA, 1995.

Download Here
First Author HomePage

Abstract:

A straightforward approach to the curse of dimensionality in reinforcement learning and dynamic programming is to replace the lookup table with a generalizing function approximator such as a neural net. Although this has been successful in the domain of backgammon, there is no guarantee of convergence. In this paper, we show that the combination of dynamic programming and function approximation is not robust, and in even very benign cases, may produce an entirely wrong policy. We then introduce Grow-Support, a new algorithm which is safe from divergence yet can still reap the benefits of successful generalization.

Keywords: Reinforcement Learning, Function Approximation, Dynammic Programming

Bibtex:

@inproceedings{ boyan95generalization,
    author = "Justin A. Boyan and Andrew W. Moore",
    title = "Generalization in Reinforcement Learning: {S}afely Approximating the Value Function",
    booktitle = "Advances in Neural Information Processing Systems 7",
    publisher = "The MIT Press",
    address = "Cambridge, MA",
    editor = "G. Tesauro and D. S. Touretzky and T. K. Leen",
    pages = "369--376",
    year = "1995",
    url = "citeseer.ist.psu.edu/boyan95generalization.html"}

Comments:

Good insights about FA within RL Framework.
In Figure 3, first graph is similar to optimum solution but then it starts to diverges. This is the same for Figure 6 first graph.
This paper is about off-policy methods (The model is provided.)
This is a big assumption that J* is in the space spanned by FA.
In my opinion the idea of grow-support algorithm is to extend the backups till reach a safe state. At the beginning it is only the final state and then it will be extended to other states. The FA should only includes safe states and their values. (This is not consistent totally with the proposed method)
There are a few concerns with the proposed algorithm.

The algorithm is dependent to the initial values. It seems to me that in order to make it work initial values should be pessimistic if epsilon is zero. If we do not have a good estimation of the final values this can be a potential problem. On the other hand setting initial values to large values might sacrifice so much time for RolloutCost function.

The RolloutCost function can be less computationally expensive by ending the search by reaching any state of the SUPPORT set instead of the goal. It might affect the accuracy even more if the environment is not deterministic though.

As state in the first part it is not clear to me that the new algorithm is less expensive.

Having deterministic transactions is less likely to be satisfied by most real environments.

The idea of binding the FA function to include only certain states in each iteration seems novel to me. (Alborz)