Piecewise-stationary bandit problems with side observations

ABSTRACT

We consider a sequential decision problem where the rewards are generated by a piecewise-stationary distribution. However, the different reward distributions are unknown and may change at unknown instants. Our approach uses a limited number of side observations on past rewards, but does not require prior knowledge of the frequency of changes. In spite of the adversarial nature of the reward process, we provide an algorithm whose regret, with respect to the baseline with perfect knowledge of the distributions and the changes, is O(k log(T)), where k is the number of changes up to time T. This is in contrast to the case where side observations are not available, and where the regret is at least Ω(√T).

REFERENCES

• 1: Akakpo, N. (2008). Detecting change-points in a discrete distribution via model selection. Preprint. http://arxiv.org/abs/0801.0970.
• 2: Peter Auer , Nicolò Cesa-Bianchi , Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, v.47 n.2-3, p.235-256, May-June 2002 [doi>10.1023/A:1013689704352]
• 3: Peter Auer , Nicolò Cesa-Bianchi , Yoav Freund , Robert E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, v.32 n.1, p.48-77, 2003 [doi>10.1137/S0097539701398375]
• 4: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 5: Eyal Even-Dar , Shie Mannor , Yishay Mansour, Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems, The Journal of Machine Learning Research, 7, p.1079-1105, 12/1/2006
• 6: Fuh, C. D. (2004). Asymptotic operating characteristics of an optimal change point detection in hidden Markov models. Ann. Statist., 2305--2339.
• 7: Garivier, A., & Moulines, E. (2008). On upper-confidence bound policies for non-stationary bandit problems. Preprint. http://arxiv.org/abs/0805. 3415.
• 8: Hartland, C., Gelly, S., Baskiotis, N., Teytaud, O., & Sebag, M. (2006). Multi-armed bandit, dynamic environments and meta-bandits. Preprint. http://hal.archives-ouvertes.fr/hal-00113668/en/.
• 9: Mark Herbster , Manfred K. Warmuth, Tracking the Best Expert, Machine Learning, v.32 n.2, p.151-178, Aug. 1998 [doi>10.1023/A:1007424614876]
• 10: Kocsis, L., & Szepesváári, C. (2006). Discounted-UCB. 2nd PASCAL Challenges Workshop.
• 11: Lai, T. L. (2001). Sequential analysis: some classical problems and new challenges. Statistica Sinica, 11, 303--408.
• 12: Lai, T. L., & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6, 4--22.
• 13: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 14: Lorden, G. (1971). Procedures for reacting to a change in distribution. Ann. Math. Statist., 42, 1897--1908.
• 15: Mei, Y. J. (2006). Sequential change-point detection when unknown parameters are present in the pre-change distribution. Ann. Statist., 34, 92--122.
• 16: Page, E. S. (1954). Continuous inspection scheme. Biometrika, 41, 100--115.
• 17: Pollak, M. (1987). Average run lengths of an optimal method of detecting a change in distribution. Ann. Statist., 15, 749--779.
• 18: Shiryayev, A. N. (1963). On optimum methods in quickest detection problems. Theory Probab. Appl., 8, 22--46.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory