Contextual Markov decision processes (CMDPs) describe a class of
reinforcement learning problems in which the transition kernels and reward
functions can change over time with different MDPs indexed by a context
variable. While CMDPs serve as an important framework to model many real-world
applications with time-varying environments, they are largely unexplored from
theoretical perspective. In this paper, we study CMDPs under two linear
function approximation models: Model I with context-varying representations and
common linear weights for all contexts; and Model II with common
representations for all contexts and context-varying linear weights. For both
models, we propose novel model-based algorithms and show that they enjoy
guaranteed $\epsilon$-suboptimality gap with desired polynomial sample
complexity. In particular, instantiating our result for the first model to the
tabular CMDP improves the existing result by removing the reachability
assumption. Our result for the second model is the first-known result for such
a type of function approximation models. Comparison between our results for the
two models further indicates that having context-varying features leads to much
better sample efficiency than having common representations for all contexts
under linear CMDPs.

该论文研究了上下文马尔可夫决策过程（CMDPs）在线性函数逼近模型下的性质，提出了创新的基于模型的算法，并证明了其在样本复杂度方面的优越性。比较两种模型的结果表明，上下文变化的特征比所有上下文共享表示在线性 CMDPs 中具有更好的样本效率。