Fast rates for online learning in Linearly Solvable Markov Decision Processes

2017-02-21 · Gergely Neu, Vicenç Gómez

We study the problem of online learning in a class of Markov decision processes known as linearly solvable MDPs. In the stationary version of this problem, a learner interacts with its environment by directly controlling the state transitions, attempting to balance a fixed state-dependent cost and a certain smooth cost penalizing extreme control inputs. In the current paper, we consider an online setting where the state costs may change arbitrarily between consecutive rounds, and the learner only observes the costs at the end of each respective round. We are interested in constructing algorithms for the learner that guarantee small regret against the best stationary control policy chosen in full knowledge of the cost sequence. Our main result is showing that the smoothness of the control cost enables the simple algorithm of following the leader to achieve a regret of order $\log^2 T$ after $T$ rounds, vastly improving on the best known regret bound of order $T^{3/4}$ for this setting.

📄 PDF Abstract BibTeX arXiv:1702.06341

Code (0)

등록된 구현이 없습니다.

Hierarchy through Composition with Linearly Solvable Markov Decision Processes

2016-12-08 · Andrew M. Saxe, Adam Earle, Benjamin Rosman

Hierarchical architectures are critical to the scalability of reinforcement learning methods. Current hierarchical frameworks execute actions serially, with macro-actions comprising sequences of primitive actions. We pro…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Hierarchical Average-Reward Linearly-solvable Markov Decision Processes

2024-07-09 · Guillermo Infante, Anders Jonsson, Vicenç Gómez

We introduce a novel approach to hierarchical reinforcement learning for Linearly-solvable Markov Decision Processes (LMDPs) in the infinite-horizon average-reward setting. Unlike previous work, our approach allows learn…

Hierarchical Reinforcement Learning reinforcement-learning Reinforcement Learning

Hierarchical Linearly-Solvable Markov Decision Problems

2016-03-10 · Anders Jonsson, Vicenç Gómez

We present a hierarchical reinforcement learning framework that formulates each task in the hierarchy as a special type of Markov decision process for which the Bellman equation is linear and has analytical solution. Pro…

Hierarchical Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processes

2021-06-29 · Guillermo Infante, Anders Jonsson, Vicenç Gómez

In this work we present a novel approach to hierarchical reinforcement learning for linearly-solvable Markov decision processes. Our approach assumes that the state space is partitioned, and the subtasks consist in movin…

Hierarchical Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

Actor-Critic for Linearly-Solvable Continuous MDP with Partially Known Dynamics

2017-06-04 · Tomoki Nishi, Prashant Doshi, Michael R. James, Danil Prokhorov

In many robotic applications, some aspects of the system dynamics can be modeled accurately while others are difficult to obtain or model. We present a novel reinforcement learning (RL) method for continuous state and ac…

Reinforcement Learning Reinforcement Learning (RL)