Linear Mixture Distributionally Robust Markov Decision Processes

Many real-world decision-making problems face the off-dynamics challenge: the agent learns a policy in a source domain and deploys it in a target domain with different state transitions. The distributionally robust Markov decision process (DRMDP) addresses this challenge by finding a robust policy that performs well under the worst-case environment within a pre-specified uncertainty set of transition dynamics. Its effectiveness heavily hinges on the proper design of these uncertainty sets, based on prior knowledge of the dynamics. In this work, we propose a novel linear mixture DRMDP framework, where the nominal dynamics is assumed to be a linear mixture model. In contrast with existing uncertainty sets directly defined as a ball centered around the nominal kernel, linear mixture DRMDPs define the uncertainty sets based on a ball around the mixture weighting parameter. We show that this new framework provides a more refined representation of uncertainties compared to conventional models based on (s, a)-rectangularity and d-rectangularity, when prior knowledge about the mixture model is present. We propose a meta algorithm for robust policy learning in linear mixture DRMDPs with general fdivergence defined uncertainty sets, and analyze its sample complexities under three divergence metrics instantiations: total variation, Kullback-Leibler, and χ 2 divergences. These results establish the statistical learnability of linear mixture DRMDPs, laying the theoretical foundation for future research on this new setting.

A commonly studied class of transition is the mixture distribution [19,2,6,58,22], which frequently arises in practice [30,35,36]. Assuming we are equipped with the prior information that the source domain transition kernels are linear mixture distributions of some basis modes ϕ(•|s, a) that we have access to, i.e., P 0 (•|s, a) = ⟨θ 0 , ϕ(•|s, a)⟩, where θ 0 is some unknown mixture weighting parameter. Then it is reasonable to hold the belief that the target domain dynamics maintains the linear mixture structure, i.e., P (•|s, a) = ⟨θ, ϕ(•|s, a)⟩, while the parameter θ is subject to some perturbation from θ 0 . This kind of perturbation cannot be precisely characterized by existing uncertainty set designs in literature. In this work, we propose the novel linear mixture uncertainty set. We formally establish a new framework for DRMDPs with linear mixture uncertainty sets, dubbed as the linear mixture DRMDP. This formulation is intrinsically different from existing frameworks due to the introduction of structural information into both the dynamics and the uncertainty set design. Focusing on the offline RL setting where we only have access to an offline dataset pre-collected from the source domain by a behavior policy π b , we provide answers to the following fundamental questions: How many samples are required to learn an ϵ-optimal robust policy for linear mixture DRMDPs?

In this paper, we provide the first ever study on linear mixture distributionally robust Markov decision processes. We summarize our main contributions as follows:

• We show that the novel design of the linear mixture uncertainty set can achieve more refined quantification of the dynamics shift compared to the standard (s, a)-rectangular and the d-rectangular uncertainty set, hence could potentially be more favorable. This justifies the need of linear mixture DRMDPs. Further, we prove that the dynamic programming principles hold for linear mixture DRMDPs, which motivate the algorithm design and theoretical analysis.

• We propose a meta algorithm based on the double pessimism principle [5] and transition targeted ridge regression [22] for linear mixture DRMDPs with general probability divergence metric defined uncertainty sets. From the theoretical side, we prove that when instantiating to the commonly studied TV, KL and χ 2 divergences, our proposed algorithm achieves upper bound on the suboptimality in order of Õ(dH

showing the statistical learnability of linear mixture DRMDPs.

1 Here d is the number of basis modes, H is the horizon length, C π ⋆ is a coverage parameter of the offline dataset (see Assumption 5.1), λ is the lower bound on the dual variable of KL-divergence (see Assumption 5.5), ρ is the uncertainty level and K is the number of samples in the offline dataset. robust Q-function are defined as V π,ρ h,P 0 (s) = inf