Online Episodic Convex Reinforcement Learning
We study online learning in episodic finite-horizon Markov decision processes (MDPs) with convex objective functions, known as the concave utility reinforcement learning (CURL) problem. This setting generalizes RL from linear to convex losses on the state-action distribution induced by the agent's policy. The non-linearity of CURL invalidates classical Bellman equations and requires new algorithmic approaches. We introduce the first algorithm achieving near-optimal regret bounds for online CURL without any prior knowledge on the transition function. To achieve this, we use an online mirror descent algorithm with varying constraint sets and a carefully designed exploration bonus. We then address for the first time a bandit version of CURL, where the only feedback is the value of the objective function on the state-action distribution induced by the agent's policy. We achieve a sub-linear regret bound for this more challenging problem by adapting techniques from bandit convex optimization to the MDP setting.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningReinforcement LearningSimilar Papers 제목 키워드 기반
Constrained episodic reinforcement learning in concave-convex and knapsack settings
We propose an algorithm for tabular episodic reinforcement learning with constraints. We provide a modular analysis with strong theoretical guarantees for settings with concave rewards and convex constraints, and for set…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Deep Reinforcement Learning: A Convex Optimization Approach
In this paper, we consider reinforcement learning of nonlinear systems with continuous state and action spaces. We present an episodic learning algorithm, where we for each episode use convex optimization to find a two-l…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningOnline Reinforcement Learning with Uncertain Episode Lengths
Existing episodic reinforcement algorithms assume that the length of an episode is fixed across time and known a priori. In this paper, we consider a general framework of episodic reinforcement learning when the length o…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Online Convex Optimization in Adversarial Markov Decision Processes
We consider online learning in episodic loop-free Markov decision processes (MDPs), where the loss function can change arbitrarily between episodes, and the transition function is not known to the learner. We show $\tild…
Memory-Efficient Episodic Control Reinforcement Learning with Dynamic Online k-means
Recently, neuro-inspired episodic control (EC) methods have been developed to overcome the data-inefficiency of standard deep reinforcement learning approaches. Using non-/semi-parametric models to estimate the value fun…
Atari GamesClusteringDeep Reinforcement LearningOnline Clustering+3