Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring
Junpei Komiyama, Junya Honda, Hiroshi Nakagawa
Abstract
Partial monitoring is a general model for sequential learning with limited feedback formalized as a game between two players. In this game, the learner chooses an action and at the same time the opponent chooses an outcome, then the learner suffers a loss and receives a feedback signal. The goal of the learner is to minimize the total loss. In this paper, we study partial monitoring with finite actions and stochastic outcomes. We derive a logarithmic distribution-dependent regret lower bound that defines the hardness of the problem. Inspired by the DMED algorithm (Honda and Takemura, 2010) for the multi-armed bandit problem, we propose PM-DMED, an algorithm that minimizes the distribution-dependent regret. PM-DMED significantly outperforms state-of-the-art algorithms in numerical experiments. To show the optimality of PM-DMED with respect to the regret bound, we slightly modify the algorithm by introducing a hinge function (PM-DMED-Hinge). Then, we derive an asymptotical optimal regret upper bound of PM-DMED-Hinge that matches the lower bound.
BibTeX
@inproceedings{NIPS2015_cd89fef7,
author = {Komiyama, Junpei and Honda, Junya and Nakagawa, Hiroshi},
booktitle = {Advances in Neural Information Processing Systems},
editor = {C. Cortes and N. Lawrence and D. Lee and M. Sugiyama and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring},
url = {https://proceedings.neurips.cc/paper_files/paper/2015/file/cd89fef7ffdd490db800357f47722b20-Paper.pdf},
volume = {28},
year = {2015}
}