PAC Bounds for Multi-armed Bandit and Markov Decision Processes

Eyal Even-Dar, Shie Mannor, Yishay MansourCOLT 2002 · OpenReview

Abstract

The bandit problem is revisited and considered under the PAC model. Our main contribution in this part is to show that given n arms, it suffices to pull the arms O(n/ε 2log1/δ) times to find an ∈-optimal arm with probability of at least 1 - δ. This is in contrast to the naive bound of O(n/ε 2logn/δ). We derive another algorithm whose complexity depends on the specific setting of the rewards, rather than the worst case setting. We also provide a matching lower bound. We show how given an algorithm for the PAC model Multi-armed Bandit problem, one can derive a batch learning algorithm for Markov Decision Processes. This is done essentially by simulating Value Iteration, and in each iteration invoking the multi-armed bandit algorithm. Using our PAC algorithm for the multi-armed bandit problem we improve the dependence on the number of actions.
BibTeX
@inproceedings{evendar2002pac,
  author = {Eyal Even-Dar and Shie Mannor and Yishay Mansour},
  title = {{PAC Bounds for Multi-armed Bandit and Markov Decision Processes}},
  booktitle = {Conference on Learning Theory},
  year = {2002},
  url = {https://openreview.net/forum?id=xL0ohYbWp_c},
}

Loading related content...

Figure