Online Markov Decision Processes

Eyal Even-Dar · Sham M. Kakade · Yishay Mansour

137 citations0/0 files storedMathematics of Operations Research

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Optimization and Search Problems

Abstract

We consider a Markov decision process (MDP) setting in which the reward function is allowed to change after each time step (possibly in an adversarial manner), yet the dynamics remain fixed. Similar to the experts setting, we address the question of how well an agent can do when compared to the reward achieved under the best stationary policy over time. We provide efficient algorithms, which have regret bounds with no dependence on the size of state space. Instead, these bounds depend only on a certain horizon time of the process and logarithmically on the number of actions.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 137 citations exist upstream.

References

1997Exponentiated Gradient versus Gradient Descent for Linear Predictors 2005Robust Control of Markov Decision Processes with Uncertain Transition Matrices 1997How to use expert advice 2004Efficient algorithms for online decision problems 1998On‐Line Portfolio Selection Using Multiplicative Updates 1995Additive versus exponentiated gradient updates for linear prediction 2002Adaptive and self-confident on-line learning algorithms 1997Universal portfolios with and without transaction costs

Cited by

2012Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret 2014Online Markov Decision Processes Under Bandit Feedback 2020Improper Learning for Non-Stochastic Control 2018Online Linear Quadratic Control 2024Corruption-Robust Exploration in Episodic Reinforcement Learning 2012The adversarial stochastic shortest path problem with unknown transition probabilities

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.