PAC Bounds for Multi-armed Bandit and Markov Decision Processes
Lists
Only you see this
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...