Deterministic MDPs with Adversarial Rewards and Bandit Feedback
This work addresses a key challenge in reinforcement learning for scenarios with adversarial rewards and limited feedback, offering a more general solution than prior methods.
The paper tackles the problem of online decision-making in deterministic Markov decision processes with adversarial rewards and bandit feedback, presenting the MarcoPolo algorithm that achieves a regret of O(T^(3/4)sqrt(log(T))) against the best deterministic policy without relying on the unichain assumption.
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.