THE NON-BAYESIAN RESTLESS MULTI-ARMED BANDIT: A CASE OF NEAR-LOGARITHMIC REGRET
Spectrum Sensing for Cognitive Radio
Přednášející: Qing Zhao, Autoři: Wenhan Dai, Tsinghua University, China; Yi Gai, Bhaskar Krishnamachari, University of Southern California, United States; Qing Zhao, University of California Davis, United States
In the classic Bayesian restless multi-armed bandit (RMAB) problem, there are $N$ arms, with rewards on all arms evolving at each time as Markov chains with known parameters. A player seeks to activate $K geq 1$ arms at each time in order to maximize the expected total reward obtained over multiple plays. RMAB is a challenging problem that is known to be PSPACE-hard in general. We consider in this work the even harder non-Bayesian RMAB, in which the parameters of the Markov chain are assumed to be unknown emph{a priori}. We develop an original approach to this problem that is applicable when the corresponding Bayesian problem has the structure that, depending on the known parameter values, the optimal solution is one of a prescribed finite set of policies. In such settings, we propose to learn the optimal policy for the non-Bayesian RMAB by employing a suitable meta-policy which treats each policy from this finite set as an arm in a different non-Bayesian multi-armed bandit problem for which a single-arm selection policy is optimal. We demonstrate this approach by developing a novel sensing policy for opportunistic spectrum access over unknown dynamic channels. We prove that our policy achieves near-logarithmic regret (the difference in expected reward compared to a model-aware genie), which leads to the same average reward that can be achieved by the optimal policy under a known model. This is the first such result in the literature for a non-Bayesian RMAB.
Informace o přednášce
| Nahráno: | 2011-05-24 14:05 - 14:25, Club E |
|---|---|
| Přidáno: | 21. 6. 2011 20:23 |
| Počet zhlédnutí: | 39 |
| Rozlišení videa: | 1024x576 px, 512x288 px |
| Délka videa: | 0:20:10 |
| Audio stopa: | MP3 [6.82 MB], 0:20:10 |
Příbuzné přednášky
0:21:01
DETECTION DIVERSITY OF MULTIANTENNA SPECTRUM SENSORS
Spectrum Sensing for Cognitive Radio
Přidáno: 22. 6. 2011 01:34
0:19:23
ON AUTOCORRELATION-BASED MULTIANTENNA SPECTRUM SENSING FOR COGNITIVE RADIOS IN UNKNOWN NOISE
Spectrum Sensing for Cognitive Radio
Přidáno: 22. 6. 2011 01:39
Komentáře