A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

概要

We study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback. The state-of-the-art result for this setting (Liu et al., 2024) either achieves $\sqrt{K}$ regret with a computationally inefficient algorithm or achieves suboptimal $K^{3/4}$ regret, where $K$ is the number of episodes. Our work gives the first $\sqrt{K}$ regret with a polynomial-time algorithm. Our method reduces adversarial linear MDPs to adversarial linear bandits whose action set consists of policies' expected feature vectors. The central challenge is that this action set is unknown and can be estimated only through exploration. We address this challenge by constructing an approximate separation oracle for the action set that either generates executable policies from queried features, or refines an outer approximation of the action set. This approach draws inspiration from the reduction of van Erven et al. (2025) for linear contextual bandits and the oracle-efficient linear bandit algorithm of Ito et al. (2019), but additionally deals with the imprecision of the oracle. The resulting algorithm requires only aggregate loss feedback, and to our knowledge. This is the first polynomial-time algorithm for adversarial MDPs with aggregate feedback beyond the tabular case.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

# 概要
We study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback. The state-of-the-art result for this setting (Liu et al., 2024) either achieves…

# 原典
https://arxiv.org/abs/2610.30801

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。