Near-Optimal Reinforcement Learning in Polynominal Time
Lists
Only you see this
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.
BibTeX
@inproceedings{kearns1998near,
author = {Michael J. Kearns and Satinder P. Singh},
title = {{Near-Optimal Reinforcement Learning in Polynominal Time}},
booktitle = {International Conference on Machine Learning},
year = {1998},
url = {https://openreview.net/forum?id=H143SsZO-B},
}Loading related content...