Deterministic MDPs with Adversarial Rewards and Bandit Feedback

Understand

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.