Policy Optimization for Adversarial Linear Mixture MDPs with Unknown Transitions and Bandit Feedback

Abstract

We study episodic reinforcement learning with adversarial losses and bandit feedback in MDPs with unknown transitions under a linear-mixture model. In this setting, prior studies are typically built upon global optimization methods with the notion of occupancy measure, rather than the purely local policy optimization-based method, which avoids solving a constrained convex optimization problem and is thus more preferred in practice. In this work, we develop the first policy optimization-based algorithm that runs online mirror descent locally on each state. The main challenge is to interface local updates with transition learning: the dilated-bonus analysis requires predictable reachability surrogates and robust one-step maximizations over a confidence set, but the statistically natural VLS confidence region is a coupled ellipsoid over a shared parameter and is not (s,a)-rectangular. We address this by rectangularizing the VLS ellipsoid into local per-(s,a) kernel sets, which enables robust dynamic programming to compute occupancy envelopes and to drive the implicit-exploration estimator and dilated bonuses. Based on this technique, we prove a high-probability regret bound 𝒪(H^3/2√(S AK) + dH^3/2 S^3/2√(K)), which nearly matches the best-known bound achieved by occupancy-measure-based methods.