Near-Optimal Reinforcement Learning in Polynomial Time
Machine LearningPublished 1 November 2002Open access
Michael Kearns, Satinder Singh
Citations858
SJR quartileQ1
SJR score1.15
SNIP2.14
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
New algorithms for reinforcement learning are presented and it is proved that they have polynomial bounds on the resources required to achieve near-optimal return in general Markov decision processes.
Abstract
We present new algorithms for reinforcement learning and prove that they have polynomial bounds on the resources required to achieve near-optimal return in general Markov decision processes. After observing that the number of actions required to approach the optimal return is lower bounded by the mixing time T of the optimal policy (in the undiscounted case) or by the horizon time T (in the discounted case), we then give algorithms requiring a number of actions and total computation time that are only polynomial in T and the number of states and actions, for both the undiscounted and discounted cases. An interesting aspect of our algorithms is their explicit handling of the Exploration-Exploitation trade-off.
Keywords
Computer Science
Machine LearningQ-learning
8,970 Citations1992Christopher J. Watkins, Peter Dayan
This paper presents and proves in detail a convergence theorem forQ-learning based on that outlined in Watkins (1989), showing that Q-learning converges to the optimum action-values with probability 1 so long as all actions are repeatedly sampled in all states and the action- values are represented discretely.
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.
Wiley series in probability and statisticsMarkov Decision Processes
5,868 Citations1994Martin L. Puterman
Machine LearningLearning to Predict by the Methods of Temporal Differences
3,894 Citations1988Richard S. Sutton
This article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior, and proves their convergence and optimality for special cases and relate them to supervised-learning methods.
Machine LearningTechnical Note: Q-Learning
3,691 Citations1992Christopher J. Watkins, Peter Dayan
A convergence theorem is presented and proves that Q -learning converges to the optimum action-values with probability 1 so long as all actions are repeatedly sampled in all states and the action- values are represented discretely.
Machine LearningLearning to predict by the methods of temporal differences
2,758 Citations1988Richard S. Sutton
On-line Q-learning Using Connectionist Systems
1,497 Citations1994G. A. Rummery
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.
Neural ComputationOn the Convergence of Stochastic Iterative Dynamic Programming Algorithms
805 Citations1994Tommi Jaakkola, Michael I. Jordan +1 more
A rigorous proof of convergence of DP-based learning algorithms is provided by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem, which establishes a general class of convergent algorithms to which both TD() and Q-learning belong.
Machine LearningPrioritized Sweeping: Reinforcement Learning with Less Data and Less Time
710 Citations1993Andrew Moore, Christopher G. Atkeson
This work presents a new algorithm, prioritized sweeping, for efficient prediction and control of stochastic Markov systems, which successfully solves large state-space real-time problems with which other methods have difficulty.
Elsevier eBooksLearning policies for partially observable environments: Scaling up
653 Citations1995Michael L. Littman, Anthony R. Cassandra +1 more
This paper discusses several simple solution methods and shows that all are capable of finding near- optimal policies for a selection of extremely small POMDP'S taken from the learning literature, but shows that none are able to solve a slightly larger and noisier problem based on robot navigation.
Machine LearningConvergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms
613 Citations2000Satinder Singh, Tommi Jaakkola +2 more
This paper examines the convergence of single-step on-policy RL algorithms for control with both decaying exploration and persistent exploration and provides examples of exploration strategies that result in convergence to both optimal values and optimal policies.
Machine LearningAsynchronous Stochastic Approximation and Q-Learning
610 Citations1994John N. Tsitsiklis
The Q-learning algorithm, a reinforcement learning method for solving Markov decision problems, is studied to establish its convergence under conditions more general than previously available.
Machine LearningReinforcement learning with replacing eligibility traces
590 Citations1996Satinder Singh, Richard S. Sutton
A new kind of eligibility trace, thereplacing trace, is introduced theoretically, analyzed theoretically, and it is shown that it results in faster, more reliable learning than the conventional trace, and that replacing traces significantly improve performance and reduce parameter sensitivity on the "Mountain-Car" task.
Elsevier eBooksStable Function Approximation in Dynamic Programming
455 Citations1995Geoffrey J. Gordon
A proof of convergence is provided for a wide class of temporal difference methods involving function approximators such as k-nearest-neighbor, and it is shown experimentally that these methods can be useful.
Machine LearningAsynchronous stochastic approximation and Q-learning
455 Citations1994John N. Tsitsiklis
The Q-learning algorithm, a reinforcement learning method for solving Markov decision problems, is studied to establish its convergence under conditions more general than previously available.
Machine LearningFeature-based methods for large scale dynamic programming
452 Citations1996John N. Tsitsiklis, Benjamin Van Roy
A methodological framework is developed and algorithms that employ two types of feature-based compact representations; that is, representations that involve feature extraction and a relatively simple approximation architecture are developed.
Machine LearningPrioritized sweeping: Reinforcement learning with less data and less time
387 Citations1993Andrew Moore, Christopher G. Atkeson
This work presents a new algorithm, prioritized sweeping, for efficient prediction and control of stochastic Markov systems, which successfully solves large state-space real-time problems with which other methods have difficulty.
Birkhäuser Boston eBooksAlgorithms for Random Generation and Counting: A Markov Chain Approach
381 Citations1993Alistair Sinclair
The Markov chain approach to generation problems and self-embeddable relations, a robust notion of approximate counting, and direct applications.
Reinforcement Learning Algorithm for Partially Observable Markov Decision Problems
353 Citations1994Tommi Jaakkola, Satinder Singh +1 more
This work proposes and analyze a new learning algorithm to solve a certain class of non-Markov decision problems and operates in the space of stochastic policies, a space which can yield a policy that performs considerably better than any deterministic policy.
Reinforcement learning with perceptual aliasing: the perceptual distinctions approach
319 Citations1992Lonnie Chrisman
The predictive distinctions approach to compensate for perceptual aliasing caused from incomplete perception of the world is introduced and Experimental results are given for a simple simulated domain, and additional issues are discussed.
Reinforcement Learning with Soft State Aggregation
269 Citations1994Satinder Singh, Tommi Jaakkola +1 more
This paper presents a function approximator based on a simple extension to state aggregation (a commonly used form of compact representation), namely soft state aggregation, a theory of convergence for RL with arbitrary, but fixed, softstate aggregation, and a novel intuitive understanding of the effect of state aggregation on online RL.
The role of exploration in learning control
227 Citations1992Sebastian Thrun
Whenever an intelligent agent learns to control an unknown environment, two opposing objectives have to be combined: the environment must be explored in order to identify a (sub-) optimal controller and experience made during learning must also be considered for action selection.
On the Convergence of Stochastic Iterative Dynamic Programming Algorithms
154 Citations1993Tommi Jaakkola, Michael I. Jordan +1 more
Efficient reinforcement learning in factored MDPs
150 Citations1999Michael Kearns, Daphne Koller
This work presents a provably efficient and near-optimal algorithm for reinforcement learning in Markov decision processes (MDPs) whose transition model can be factored as a dynamic Bayesian network (DBN).
Feature-Based Methods for Large Scale Dynamic Programming
87 Citations1996John N. Tsitsiklis, Benjamin Van Roy
Efficient reinforcement learning
74 Citations1994Claude-Nicolas Fiechter
A new formal model for studying reinforcement learning, based on Valiant's PAC framework, that requires the learner to produce a policy whose expected value from the initial state is ε-close to that of the optimal policy, with probability no less than 1−δ.
Reinforcement Learning with Replacing Eligibility Traces
63 Citations2007Satinder Singh, Richard S. Sutton
neural information processing systemsSequential Decision Problems and Neural Networks
60 Citations1989Andrew G. Barto, Richard S. Sutton +1 more
This paper discusses reinforcement learning in terms of the sequential decision framework and shows how a learning algorithm similar to the one implemented by the Adaptive Critic Element used in the pole-balancer of Barto, Sutton, and Anderson (1983), and further developed by Sutton (1984), fits into this framework.
Machine LearningAnalytical Mean Squared Error Curves for Temporal Difference Learning
46 Citations1998Satinder Singh, Peter Dayan
It is shown that although the various temporal difference algorithms are quite sensitive to the choice of step-size and eligibility-trace parameters, there are values of these parameters that make them similarly competent, and generally good.
Feature-based methods for large scale dynamic programming
36 Citations2002J.N. Tsitsiklis, B. Van Roy
Machine LearningOn the worst-case analysis of temporal-difference learning algorithms
35 Citations1996Robert E. Schapire, Manfred K. Warmuth
Lower bounds on the performance of any algorithm for this learning problem are proved, and a similar analysis of the closely related problem of learning to predict in a model in which the learner must produce predictions for a whole batch of observations before receiving reinforcement is given.
Neural Information Processing SystemsConvergence of Indirect Adaptive Asynchronous Value Iteration Algorithms
32 Citations1993Vijaykumar Gullapalli, Andrew G. Barto
This paper presents a convergence result for indirect adaptive asynchronous value iteration algorithms for the case in which a look-up table is used to store the value function and implies convergence of several existing reinforcement learning algorithms.
Expected Mistake Bound Model for On-Line Reinforcement Learning
23 Citations1997Claude-Nicolas Fiechter
A model of eecient on-line reinforcement learning based on the expected mistake bound framework introduced by Haussler, Littlestone and Warmuth (1987) is proposed and it is shown that this model is polynomially equivalent to the PAC model of oo- line reinforcement learning introduced in (Fiechter, 1994).
A distributed asynchronous algorithm for expected average cost dynamic programming
7 Citations1990A. Jalali, Michael J. Ferguson
A distributed asynchronous implementation of the value-iteration algorithm in dynamic programming is presented, where each processor transmits its computed coordinates to other processors and the algorithm converges when the different processors iterate at different speeds.
Elsevier eBooksOn the Worst-case Analysis of Temporal-difference Learning Algorithms
4 Citations1994Robert E. Schapire, Manfred K. Warmuth
Learning curve bounds for a Markov decision process with undiscounted rewards
3 Citations1996Lawrence K. Saul, Satinder Singh
This work studies how the agent’s performance depends on the allowed exploration time in Markov decision processes, and compute a lower bound on the return of policies that appear optimal based on imperfect statistics.