Chasing Ghosts: Competing with Stateful Policies

DOI10.1137/14100227XzbMATH Open1410.91168arXiv1407.7635MaRDI QIDQ2968152FDOQ2968152

Authors: Tomer Koren, Moshe Tennenholtz, Uriel Feige 

Publication date: 10 March 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: We consider sequential decision making in a setting where regret is measured with respect to a set of stateful reference policies, and feedback is limited to observing the rewards of the actions performed (the so called "bandit" setting). If either the reference policies are stateless rather than stateful, or the feedback includes the rewards of all actions (the so called "expert" setting), previous work shows that the optimal regret grows like $Theta(sqrtT)$ in terms of the number of decision rounds $T$. The difficulty in our setting is that the decision maker unavoidably loses track of the internal states of the reference policies, and thus cannot reliably attribute rewards observed in a certain round to any of the reference policies. In fact, in this setting it is impossible for the algorithm to estimate which policy gives the highest (or even approximately highest) total reward. Nevertheless, we design an algorithm that achieves expected regret that is sublinear in $T$, of the form $O(T/lo{g}^{1/4}T)$. Our algorithm is based on a certain local repetition lemma that may be of independent interest. We also show that no algorithm can guarantee expected regret better than $O(T/lo{g}^{3/2}T)$.

Full work available at URL: https://arxiv.org/abs/1407.7635

Recommendations

• State-policy dynamics in evolutionary games
• Foundations of Software Science and Computation Structures
• Extreme state aggregation beyond MDPs
• On the Complexity of Reasoning About Dynamic Policies
• A state space distribution policy based on abstract interpretation
• State observation accuracy and finite-memory policy performance
• Learning with policy prediction in continuous state-action multi-agent decision processes

zbMATH Keywords

sequential decision makingonline learningmultiarmed banditbandit feedbackstateful policies

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Online algorithms; streaming algorithms (68W27) Decision theory (91B06) Analysis of algorithms and problem complexity (68Q25) Probabilistic games; gambling (91A60)

Cites Work

• A decision-theoretic generalization of on-line learning and an application to boosting
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Prediction, Learning, and Games
• Algorithmic Game Theory
• The Nonstochastic Multiarmed Bandit Problem
• How to use expert advice
• Universal prediction of individual sequences
• Universal prediction
• Combining expert advice in reactive environments
• On sequential strategies for loss functions with memory
• Online Markov decision processes
• Bandits with switching costs, \(T^{2/3}\) regret
• Differential privacy under continual observation
• Online Markov Decision Processes Under Bandit Feedback
• Why are images smooth?
• High-confidence predictions under adversarial uncertainty

Cited In (3)

• Quasi-random words and limits of word sequences
• One-sided epsilon-approximants
• A new bandit setting balancing information from state evolution and corrupted context

Uses Software

• AdaBoost.MH

This page was built for publication: Chasing Ghosts: Competing with Stateful Policies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968152)