Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions
One of the most natural approaches to reinforcement learning (RL) with function approximation is value iteration, which inductively generates approximations to the optimal value function by solving a sequence of regression problems. To ensure the success of value iteration, it is typically assumed that Bellman completeness holds, which ensures that these regression problems are well-specified. We study the problem of learning an optimal policy under Bellman completeness in the online model of RL with linear function approximation. In the linear setting, while statistically efficient algorithms are known under Bellman completeness (e.g., Jiang et al. (2017); Zanette et al. (2020)), these algorithms all rely on the principle of global optimism which requires solving a nonconvex optimization problem. In particular, it has remained open as to whether computationally efficient algorithms exist. In this paper we give the first polynomial-time algorithm for RL under linear Bellman completeness when the number of actions is any constant.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Fitted Q-Evaluation without Bellman Completeness via Occupancy Weighting
Fitted \(Q\)-evaluation (FQE) is a standard regression-based method for off-policy evaluation, but under distribution shift, value-function realizability alone does not ensure convergence, and existing analyses often req…
When is Realizability Sufficient for Off-Policy Reinforcement Learning?
Model-free algorithms for reinforcement learning typically require a condition called Bellman completeness in order to successfully operate off-policy with function approximation, unless additional conditions are met. Ho…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
In this paper, we study the offline RL problem with linear function approximation. Our main structural assumption is that the MDP has low inherent Bellman error, which stipulates that linear value functions have linear B…
Offline RLEnd-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying \emph{linear Bellman completeness} -- a fundamental setting where the Bellman backup of any linear va…
Reinforcement LearningSoft Fitted Q-Iteration without Bellman Completeness: Occupancy Reweighting and Temperature Annealing
Fitted \(Q\)-iteration (FQI) is a standard regression-based method for optimal control in offline reinforcement learning, but its stability under function approximation often relies on Bellman completeness, which require…
Reinforcement Learning