Stable Dual Dynamic Programming

Published 3 December 2007

Tao Wang, Michael Bowling, Dale Schuurmans, Daniel J. Lizotte

Citations26

TL;DR

This paper investigates the convergence properties of these dual algorithms both theoretically and empirically, and shows how they can be scaled up by incorporating function approximation.

Abstract

Recently, we have introduced a novel approach to dynamic programming and reinforcement learning that is based on maintaining explicit representations of stationary distributions instead of value functions. In this paper, we investigate the convergence properties of these dual algorithms both theoretically and empirically, and show how they can be scaled up by incorporating function approximation. 1

Keywords

Computer ScienceDecision Sciences

IEEE Transactions on Neural NetworksReinforcement Learning: An Introduction

25,692 Citations2005

Journal of the American Statistical AssociationMarkov Decision Processes: Discrete Stochastic Dynamic Programming.

8,422 Citations1995Kasra Hazeghi, Martin L. Puterman

Markov Decision Processes covers recent research advances in such areas as countable state space models with average reward criterion, constrained models, and models with risk sensitive optimality criteria, and explores several topics that have received little or no attention in other books.

MIT Press eBooksIntroduction to Reinforcement Learning

6,868 Citations1998Richard S. Sutton, Andrew G. Barto

In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning.

IEEE Transactions on Automatic ControlAn analysis of temporal-difference learning with function approximation

1,202 Citations1997John N. Tsitsiklis, Benjamin Van Roy

It is proved that divergence may occur when updates are not based on trajectories of the Markov chain, which reconciles positive and negative results that have been discussed in the literature, regarding the soundness of temporal-difference learning.

View PDF

Generalization in Reinforcement Learning: Successful Examples Using Sparse Coarse Coding

1,065 Citations1995Richard S. Sutton

It is concluded that reinforcement learning can work robustly in conjunction with function approximators and that there is little justi cation at present for avoiding the case of general Reinforcement Learning and Function Approximation.

Elsevier eBooksResidual Algorithms: Reinforcement Learning with Function Approximation

953 Citations1995Leemon C. Baird

Both direct and residual gradient algorithms are shown to be special cases of residual algorithms, and it is shown that residual algorithms can combine the advantages of each approach.

Generalization in Reinforcement Learning: Safely Approximating the Value Function

506 Citations1994Justin A. Boyan, Andrew Moore

Grow-Support is introduced, a new algorithm which is safe from divergence yet can still reap the benefits of successful generalization, and which is not robust, and in even very benign cases, may produce an entirely wrong policy.

Journal of Optimization Theory and ApplicationsOn the Existence of Fixed Points for Approximate Value Iteration and Temporal-Difference Learning

70 Citations2000Daniela Pucci de Farias, Benjamin Van Roy

It is shown that, in general, the modified dynamic programming operator need not possess a fixed point; therefore, approximate value iteration should not be expected to converge and a variant of approximatevalue iteration is proposed for which the associated operator is guaranteed to possess at least one fixed point.

Dual Representations for Dynamic Programming and Reinforcement Learning

31 Citations2007Tao Wang, Michael Bowling +1 more

This paper presents a modified dual of the standard linear program that guarantees a globally normalized state visit distribution is obtained, and derives novel dual forms of dynamic programming, including policy evaluation, policy iteration and value iteration to derive new forms of Sarsa and Q-learning.