Regularized Q-Learning with Linear Function Approximation
Regularized Markov Decision Processes serve as models of sequential decision making under uncertainty wherein the decision maker has limited information processing capacity and/or aversion to model ambiguity. With functional approximation, the convergence properties of learning algorithms for regularized MDPs (e.g. soft Q-learning) are not well understood because the composition of the regularized Bellman operator and a projection onto the span of basis vectors is not a contraction with respect to any norm. In this paper, we consider a bi-level optimization formulation of regularized Q-learning with linear functional approximation. The {\em lower} level optimization problem aims to identify a value function approximation that satisfies Bellman's recursive optimality condition and the {\em upper} level aims to find the projection onto the span of basis vectors. This formulation motivates a single-loop algorithm with finite time convergence guarantees. The algorithm operates on two time-scales: updates to the projection of state-action values are slow' in that they are implemented with a step size that is smaller than the one used for faster' updates of approximate solutions to Bellman's recursive optimality equation. We show that, under certain assumptions, the proposed algorithm converges to a stationary point in the presence of Markovian noise. In addition, we provide a performance guarantee for the policies derived from the proposed algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision Making Under UncertaintyQ-LearningSequential Decision MakingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation
Natural policy gradient (NPG) methods with entropy regularization achieve impressive empirical success in reinforcement learning problems with large state-action spaces. However, their convergence properties and the impa…
Analysis of Regularized Learning in Banach Spaces for Linear-functional Data
This article delves into the study of the theory of regularized learning in Banach spaces for linear-functional data. It encompasses discussions on representer theorems, pseudo-approximation theorems, and convergence the…
An Analysis of State-Relevance Weights and Sampling Distributions on L1-Regularized Approximate Linear Programming Approximation Accuracy
Recent interest in the use of $L_1$ regularization in the use of value function approximation includes Petrik et al.'s introduction of $L_1$-Regularized Approximate Linear Programming (RALP). RALP is unique among $L_1$-r…
Periodic Regularized Q-Learning
In reinforcement learning (RL), Q-learning is a fundamental algorithm whose convergence is guaranteed in the tabular setting. However, this convergence guarantee does not hold under linear function approximation. To over…
Reinforcement LearningOn Gaussian approximation for entropy-regularized Q-learning with function approximation
In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak--Ruppert averaged iterates generated by entropy-regularized asynchronous Q-learning with linear function approximatio…