From the archives
Optimally Sensing a Single Channel Without Prior Information: The Tiling Algorithm and Regret Bounds
Historical material. Affiliations, schedules and roles on this page describe their original context.
JournalName: IEEE Journal of Selected Topics in Signal Processing
Date: February, 2011
PageStart: 68
PageEnd: 76
Arxiv Number: 0908.0319
Hal Number: 00408867
Authors: Sarah FilippiOlivier CappéAurélien Garivier
Abstract: We consider the task of optimally sensing a two-state Markovian
channel with an observation cost and without any prior information regarding the channel's
transition probabilities. This task is of interest in the field of cognitive radio as a
model for opportunistic access to a communication network by a secondary user. The optimal
sensing problem may be cast into the framework of model-based reinforcement learning in a
specific class of partially observable Markov decision processes (POMDPs). We propose the
Tiling Algorithm, an original method aimed at reaching an optimal tradeoff between the
exploration (or estimation) and exploitation requirements. It is shown that this algorithm
achieves finite horizon regret bounds that are as good as those recently obtained for
multi-armed bandits and finite-state Markov decision processes (MDPs).
Direct link: available on IEEE Xplore
Issue: 1
Volume: 5
Keywords:
