Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs
This addresses a key open question in adversarial RL by providing the first horizon-free algorithm, which is significant for researchers and practitioners in reinforcement learning dealing with non-stationary environments.
The paper tackles the problem of achieving horizon-free regret bounds in adversarial reinforcement learning with linear mixture MDPs, proposing a policy search algorithm that achieves an $ ilde{O}ig((d+\log (|\mathcal{S}|^2 |\mathcal{A}|))\sqrt{K}ig)$ regret with full-information feedback, where $d$ is the feature dimension and $K$ is the number of episodes.
Recent studies have shown that episodic reinforcement learning (RL) is no harder than bandits when the total reward is bounded by $1$, and proved regret bounds that have a polylogarithmic dependence on the planning horizon $H$. However, it remains an open question that if such results can be carried over to adversarial RL, where the reward is adversarially chosen at each episode. In this paper, we answer this question affirmatively by proposing the first horizon-free policy search algorithm. To tackle the challenges caused by exploration and adversarially chosen reward, our algorithm employs (1) a variance-uncertainty-aware weighted least square estimator for the transition kernel; and (2) an occupancy measure-based technique for the online search of a \emph{stochastic} policy. We show that our algorithm achieves an $\tilde{O}\big((d+\log (|\mathcal{S}|^2 |\mathcal{A}|))\sqrt{K}\big)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|\mathcal{S}|$ and $|\mathcal{A}|$ are the cardinalities of the state and action spaces. We also provide hardness results and regret lower bounds to justify the near optimality of our algorithm and the unavoidability of $\log|\mathcal{S}|$ and $\log|\mathcal{A}|$ in the regret bound.