Reinforcement Learning algorithms for regret minimization in structured Markov Decision Processes

2016-08-17 · K J Prabuchandran, Tejas Bodas, Theja Tulabandhula

A recent goal in the Reinforcement Learning (RL) framework is to choose a sequence of actions or a policy to maximize the reward collected or minimize the regret incurred in a finite time horizon. For several RL problems in operation research and optimal control, the optimal policy of the underlying Markov Decision Process (MDP) is characterized by a known structure. The current state of the art algorithms do not utilize this known structure of the optimal policy while minimizing regret. In this work, we develop new RL algorithms that exploit the structure of the optimal policy to minimize regret. Numerical experiments on MDPs with structured optimal policies show that our algorithms have better performance, are easy to implement, have a smaller run-time and require less number of random number generations.

📄 PDF Abstract BibTeX arXiv:1608.04929

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Regret Minimization and Convergence to Equilibria in General-sum Markov Games

2022-07-28 · Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren 외

An abundance of recent impossibility results establish that regret minimization in Markov games with adversarial opponents is both statistically and computationally intractable. Nevertheless, none of these results preclu…

The Partially Observable History Process

2021-11-15 · Dustin Morrill, Amy R. Greenwald, Michael Bowling

We introduce the partially observable history process (POHP) formalism for reinforcement learning. POHP centers around the actions and observations of a single agent and abstracts away the presence of other players witho…

Form reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Test-Time Regret Minimization in Meta Reinforcement Learning

2024-06-04 · Mirco Mutti, Aviv Tamar

Meta reinforcement learning sets a distribution over a set of tasks on which the agent can train at will, then is asked to learn an optimal policy for any test task efficiently. In this paper, we consider a finite set of…

Meta Reinforcement Learning reinforcement-learning Reinforcement Learning

Differentially Private Regret Minimization in Episodic Markov Decision Processes

2021-12-20 · Sayak Ray Chowdhury, Xingyu Zhou

We study regret minimization in finite horizon tabular Markov decision processes (MDPs) under the constraints of differential privacy (DP). This is motivated by the widespread applications of reinforcement learning (RL) …

Decision Making Reinforcement Learning (RL)Sequential Decision Making

Local Differential Privacy for Regret Minimization in Reinforcement Learning

2020-10-15 · NeurIPS 2021 12 · Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, Matteo Pirotta

Reinforcement learning algorithms are widely used in domains where it is desirable to provide a personalized service. In these domains it is common that user data contains sensitive information that needs to be protected…