VO$Q$L: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation
We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic $Q$-Learning (VO$Q$L), based on $Q$-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VO$Q$L achieves $\tilde{O}(d\sqrt{HT}+d^6H^{5})$ regret over $T$ episodes for a horizon $H$ MDP under ($d$-dimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.
Code (0)
등록된 구현이 없습니다.
Tasks
Q-LearningregressionReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning
Offline reinforcement learning (RL), where the agent aims to learn the optimal policy based on the data collected by a behavior policy, has attracted increasing attention in recent years. While offline RL with linear fun…
Offline RLreinforcement-learningReinforcement LearningReinforcement Learning (RL)A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
Recently, model-free reinforcement learning has attracted research attention due to its simplicity, memory and computation efficiency, and the flexibility to combine with function approximation. In this paper, we propose…
Q-Learningreinforcement-learningReinforcement Learning (RL)Global Closed-form Approximation of Free Boundary for Optimal Investment Stopping Problems
In this paper we study a utility maximization problem with both optimal control and optimal stopping in a finite time horizon. The value function can be characterized by a variational equation that involves a free bounda…
FormKernelized Reinforcement Learning with Order Optimal Regret Bounds
Reinforcement learning (RL) has shown empirical success in various real world settings with complex models and large state-action spaces. The existing analytical results, however, typically focus on settings with a small…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation
The exploration-exploitation dilemma has been a central challenge in reinforcement learning (RL) with complex model classes. In this paper, we propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQ…
Q-LearningReinforcement Learning (RL)