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

Yutian Cheng, Canzhe Zhao, Shuai Li
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1249-1270, 2026.

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 $\widetilde{\mathcal{O}}\big(H^{3/2}\sqrt{S AK} + dH^{3/2} S^{3/2}\sqrt{K}\big)$, which nearly matches the best-known bound achieved by occupancy-measure-based methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-cheng26b, title = {Policy Optimization for Adversarial Linear Mixture {MDPs} with Unknown Transitions and Bandit Feedback}, author = {Cheng, Yutian and Zhao, Canzhe and Li, Shuai}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1249--1270}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/cheng26b/cheng26b.pdf}, url = {https://proceedings.mlr.press/v337/cheng26b.html}, 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 $\widetilde{\mathcal{O}}\big(H^{3/2}\sqrt{S AK} + dH^{3/2} S^{3/2}\sqrt{K}\big)$, which nearly matches the best-known bound achieved by occupancy-measure-based methods.} }
Endnote
%0 Conference Paper %T Policy Optimization for Adversarial Linear Mixture MDPs with Unknown Transitions and Bandit Feedback %A Yutian Cheng %A Canzhe Zhao %A Shuai Li %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-cheng26b %I PMLR %P 1249--1270 %U https://proceedings.mlr.press/v337/cheng26b.html %V 337 %X 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 $\widetilde{\mathcal{O}}\big(H^{3/2}\sqrt{S AK} + dH^{3/2} S^{3/2}\sqrt{K}\big)$, which nearly matches the best-known bound achieved by occupancy-measure-based methods.
APA
Cheng, Y., Zhao, C. & Li, S.. (2026). Policy Optimization for Adversarial Linear Mixture MDPs with Unknown Transitions and Bandit Feedback. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1249-1270 Available from https://proceedings.mlr.press/v337/cheng26b.html.

Related Material