Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition
<|reference_start|>Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition: We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses in the bandit feedback setting. Specifically, we focus on linear mixture MDPs whose transition kernel is a linear mixture model. We propose a new algorithm that attains an $\widetilde{O}(d\sqrt{HS^3K} + \sqrt{HSAK})$ regret with high probability, where $d$ is the dimension of feature mappings, $S$ is the size of state space, $A$ is the size of action space, $H$ is the episode length and $K$ is the number of episodes. Our result strictly improves the previous best-known $\widetilde{O}(dS^2 \sqrt{K} + \sqrt{HSAK})$ result in Zhao et al. (2023a) since $H \leq S$ holds by the layered MDP structure. Our advancements are primarily attributed to (i) a new least square estimator for the transition parameter that leverages the visit information of all states, as opposed to only one state in prior work, and (ii) a new self-normalized concentration tailored specifically to handle non-independent noises, originally proposed in the dynamic assortment area and firstly applied in reinforcement learning to handle correlations between different states.<|reference_end|>
@article{li2024improved,
    title={Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
  Feedback and Unknown Transition},
    author={Long-Fei Li, Peng Zhao, Zhi-Hua Zhou},
    journal={arXiv preprint arXiv:2403.04568},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04568},
    primaryClass={cs.LG stat.ML}
}