Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions
This addresses the challenge of robust online decision-making in dynamic environments, though it is incremental as it relies on specific conditions and leaves the general case open.
The paper tackles the problem of learning Markov decision processes with adversarially chosen transition probabilities and loss functions over time, introducing an algorithm that achieves regret growing as the square root of the number of rounds under a uniform mixing condition.
We study the problem of learning Markov decision processes with finite state and action spaces when the transition probability distributions and loss functions are chosen adversarially and are allowed to change with time. We introduce an algorithm whose regret with respect to any policy in a comparison class grows as the square root of the number of rounds of the game, provided the transition probabilities satisfy a uniform mixing condition. Our approach is efficient as long as the comparison class is polynomial and we can compute expectations over sample paths for each policy. Designing an efficient algorithm with small regret for the general case remains an open problem.