Deterministic MDPs with Adversarial Rewards and Bandit Feedback

Raman Arora, Ofer Dekel, Ambuj Tewari
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:90-99, 2012.

Abstract

We consider a Markov decision process with deterministic state transition dynamics, adversarially generated rewards that change arbitrarily from round to round, and a bandit feedback model in which the decision maker only observes the rewards it receives. In this setting, we present a novel and efficient online decision making algorithm named MarcoPolo. Under mild assumptions on the structure of the transition dynamics, we prove that MarcoPolo enjoys a regret of O(T^(3/4)sqrt(log(T))) against the best deterministic policy in hindsight. Specifically, our analysis does not rely on the stringent unichain assumption, which dominates much of the previous work on this topic.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-arora12a, title = {Deterministic MDPs with Adversarial Rewards and Bandit Feedback}, author = {Arora, Raman and Dekel, Ofer and Tewari, Ambuj}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {90--99}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/arora12a/arora12a.pdf}, url = {https://proceedings.mlr.press/r10/arora12a.html}, abstract = {We consider a Markov decision process with deterministic state transition dynamics, adversarially generated rewards that change arbitrarily from round to round, and a bandit feedback model in which the decision maker only observes the rewards it receives. In this setting, we present a novel and efficient online decision making algorithm named MarcoPolo. Under mild assumptions on the structure of the transition dynamics, we prove that MarcoPolo enjoys a regret of O(T^(3/4)sqrt(log(T))) against the best deterministic policy in hindsight. Specifically, our analysis does not rely on the stringent unichain assumption, which dominates much of the previous work on this topic.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Deterministic MDPs with Adversarial Rewards and Bandit Feedback %A Raman Arora %A Ofer Dekel %A Ambuj Tewari %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-arora12a %I PMLR %P 90--99 %U https://proceedings.mlr.press/r10/arora12a.html %V R10 %X We consider a Markov decision process with deterministic state transition dynamics, adversarially generated rewards that change arbitrarily from round to round, and a bandit feedback model in which the decision maker only observes the rewards it receives. In this setting, we present a novel and efficient online decision making algorithm named MarcoPolo. Under mild assumptions on the structure of the transition dynamics, we prove that MarcoPolo enjoys a regret of O(T^(3/4)sqrt(log(T))) against the best deterministic policy in hindsight. Specifically, our analysis does not rely on the stringent unichain assumption, which dominates much of the previous work on this topic. %Z Reissued by PMLR on 04 October 2026.
APA
Arora, R., Dekel, O. & Tewari, A.. (2012). Deterministic MDPs with Adversarial Rewards and Bandit Feedback. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:90-99 Available from https://proceedings.mlr.press/r10/arora12a.html. Reissued by PMLR on 04 October 2026.

Related Material