Near-Optimal Reinforcement Learning in Polynominal Time

Michael J. Kearns, Satinder P. SinghICML 1998 · OpenReview

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...

Figure