Author name cluster

Michael Duff

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

NeurIPS Conference 1996 Conference Paper

Local Bandit Approximation for Optimal Learning Problems

Michael Duff
Andrew Barto

In general, procedures for determining Bayes-optimal adaptive controls for Markov decision processes (MDP's) require a pro(cid: 173) hibitive amount of computation-the optimal learning problem is intractable. This paper proposes an approximate approach in which bandit processes are used to model, in a certain "local" sense, a given MDP. Bandit processes constitute an important subclass of MDP's, and have optimal learning strategies (defined in terms of Gittins indices) that can be computed relatively efficiently. Thus, one scheme for achieving approximately-optimal learning for gen(cid: 173) eral MDP's proceeds by taking actions suggested by strategies that are optimal with respect to local bandit models.

PDF Details

NeurIPS Conference 1994 Conference Paper

Reinforcement Learning Methods for Continuous-Time Markov Decision Problems

Steven Bradtke
Michael Duff

Semi-Markov Decision Problems are continuous time generaliza(cid: 173) tions of discrete time Markov Decision Problems. A number of reinforcement learning algorithms have been developed recently for the solution of Markov Decision Problems, based on the ideas of asynchronous dynamic programming and stochastic approxima(cid: 173) tion. Among these are TD(, x), Q-Iearning, and Real-time Dynamic Programming. After reviewing semi-Markov Decision Problems and Bellman's optimality equation in that context, we propose al(cid: 173) gorithms similar to those named above, adapted to the solution of semi-Markov Decision Problems. We demonstrate these algorithms by applying them to the problem of determining the optimal con(cid: 173) trol for a simple queueing system. We conclude with a discussion of circumstances under which these algorithms may be usefully ap(cid: 173) plied.

PDF Details

NeurIPS Conference 1993 Conference Paper

Monte Carlo Matrix Inversion and Reinforcement Learning

Andrew Barto
Michael Duff

We describe the relationship between certain reinforcement learn(cid: 173) ing (RL) methods based on dynamic programming (DP) and a class of unorthodox Monte Carlo methods for solving systems of linear equations proposed in the 1950's. These methods recast the solu(cid: 173) tion of the linear system as the expected value of a statistic suitably defined over sample paths of a Markov chain. The significance of our observations lies in arguments (Curtiss, 1954) that these Monte Carlo methods scale better with respect to state-space size than do standard, iterative techniques for solving systems of linear equa(cid: 173) tions. This analysis also establishes convergence rate estimates. Because methods used in RL systems for approximating the evalu(cid: 173) ation function of a fixed control policy also approximate solutions to systems of linear equations, the connection to these Monte Carlo methods establishes that algorithms very similar to TD algorithms (Sutton, 1988) are asymptotically more efficient in a precise sense than other methods for evaluating policies. Further, all DP-based RL methods have some of the properties of these Monte Carlo al(cid: 173) gorithms, which suggests that although RL is often perceived to be slow, for sufficiently large problems, it may in fact be more ef(cid: 173) ficient than other known classes of methods capable of producing the same results.

PDF Details