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. Let X be a finite state space and A be a finite action space. Let ∆ S be the space of probability distributions over set S. Define a policy π as a mapping from the state space to ∆ A , π : X → ∆ A . We use π(a|x) to denote the probability of choosing action a in state x under policy π. A random action under policy π is denoted by π(x). A transition probability kernel (or transition model) m is a mapping from the direct product of the state and action spaces to ∆ X : m : X × A → ∆ X . Let P (π, m) be the transition probability matrix of policy π under transition model m. A loss function is a bounded real-valued function over state and action spaces, ℓ : X × A → R. For a vector v, define v 1 = i |v i |. For a real-valued function f defined over X × A, define f ∞,1 = max x∈X a∈A |f (x, a)|. The inner product between two vectors v and w is denoted by v, w . Consider the following game between a learner and an adversary: at round t, the learner chooses a policy π t from a policy class Π. In response, the adversary chooses a transition model m t from a set of models M and a loss function ℓ t . The learner takes action a t ∼ π t (.|x t ), moves to state x t+1 ∼ m t (.|x t , a t ) and suffers loss ℓ t (x t , a t ). To simplify the discussion, we assume that the adversary is oblivious, i.e. its choices do not depend on the previous choices of the learner. We assume that ℓ t ∈ [0, 1]. In this paper, we study the full-information version of the game, where the learner observes the transition model m t and the loss function ℓ t at the end of round t. The game is shown in Figure 1 . The objective of the learner is to suffer low loss over a period of T rounds, while the performance of the learner is measured using its regret with respect to the total loss he would have achieved had he followed the stationary policy in the comparison class Π minimizing the total loss. Even-Dar et al. (2004) prove a hardness result for MDP problems with adversarially chosen transition models. Their proof, however, seems to have gaps as it assumes that the learner chooses a deterministic policy before observing the state at each round. Note that an online learning algorithm only needs to choose an action at the current state and does not need to construct a complete deterministic policy at each round. Their hardness result applies to deterministic transition models, while we make a mixing assumption in our analysis. Thus, it is still an open problem whether it is possible to obtain a computationally efficient algorithm with a sublinear regret. Yu and Mannor (2009a,b) study the same setting, but obtain only a regret bound that scales with the amount of variation in the transition models. This regret bound can grow linearly with time.
REF consider MDP problems with (oblivious) adversarial changes in state-transition probabilities and reward functions and provide algorithms for minimizing the regret with respect to a comparison set of stationary (expert) policies.
Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions
ArXiv
ArXiv
Mathematics Computer Science