We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full-information loss feedback with unknown transitions (Zhao et al., 2024), or bandit loss feedback with known transition (Foster et al., 2022). First, we improve the $poly(d, A, H)T^{5/6}$ regret bound of Zhao et al. (2024) to $poly(d, A, H)T^{2/3}$ for the full-information unknown transition setting, where d is the rank of the transitions, A is the number of actions, H is the horizon length, and T is the number of episodes. Next, we initiate the study on the setting with bandit loss feedback and unknown transitions. Assuming that the loss has a linear structure, we propose both model based and model free algorithms achieving $poly(d, A, H)T^{2/3}$ regret, though they are computationally inefficient. We also propose oracle-efficient model-free algorithms with $poly(d, A, H)T^{4/5}$ regret. We show that the linear structure is necessary for the bandit case without structure on the reward function, the regret has to scale polynomially with the number of states. This is contrary to the full-information case (Zhao et al., 2024), where the regret can be independent of the number of states even for unstructured reward function.

本研究解决了低秩马尔可夫决策过程中的遗憾最小化问题，聚焦于未知转移的全信息损失反馈和带宽损失反馈的设置。论文提出改进的算法，使得在全信息未知转移情况下的遗憾界限达到$poly(d, A, H)T^{2/3}$，并首次探讨了在带宽损失反馈与未知转移的条件下的算法，揭示线性结构对带宽情况下的必要性，对比全信息情况下的不同表现。

在未知转移和带宽反馈下击败对抗性低秩马尔可夫决策过程