Optimal Adaptive Policies for Markov Decision Processes

By Apostolos N. Burnetas, Michael N. Katehakis. 1997

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, background): “We consider a well-studied reinforcement learning problem in which an agent interacts with a Markov decision process with the aim of maximizing expected cumulative reward [25, 6].”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “Although Burnetas and Katehakis [56] prove an even more general lower bound, Theorem 2.”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, background): “As the agent interacts with its environment, it observes the outcomes that result from previous states and actions, and learns about the system dynamics.”
A unified view of entropy-regularized Markov decision processes (2017, neutral): “We ﬁrst provide a counterpart to the performance-diﬀerence lemma (Burnetas and Katehakis, 1997, Prop.”
Minimax Regret Bounds for Reinforcement Learning (2017, background): “M L ] 1 J ul 2 We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs.”
Near-optimal Reinforcement Learning in Factored MDPs (2014, neutral): “We consider a reinforcement learning agent that takes sequential actions within an uncertain environment with an aim to maximize cumulative reward [1].”
Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs (2018, background): “One of the first algorithms based on this principle for MDPs is due to (Burnetas and Katehakis, 1997), which is shown to be asymptotically optimal.”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, background): “Their algorithm leverages ideas from asymptotic optimal algorithms in structured bandits [15] and tabular RL [16], but does not scale to continuous state-action spaces.”
Learning Deep Mean Field Games for Modeling Large Population Behavior (2017, background): “Methods in unknown MDP estimation and inverse reinforcement learning aim to learn an optimal policy while estimating an unknown quantity of the MDP, such as the transition law (Burnetas & Katehakis, 1997), secondary parameters (Budhiraja et al., 2012), and the reward function (Ng & Russell, 2000).”
Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning (2006, background): “Another paper with a similar approach is Burnetas, Katehakis [13].”
Regret Bounds for Reinforcement Learning via Markov Chain Concentration (2018, background): “Some of these bounds like the one derived in the mentioned [9] depend on particular properties of the underlying MDP, typically some kind of gap that specifies the distance between an optimal and a sub-optimal action or policy (see e.”
Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (2020, background): “RL in stationary (discounted and un-discounted reward) MDPs has been widely studied in (Burnetas & Katehakis, 1997; Bartlett & Tewari, 2009; Jaksch et al., 2010; Agrawal & Jia, 2017; Fruit et al., 2018a;b; Sidford et al., 2018b;a; Wang, 2019; Zhang & Ji, 2019; Fruit et al., 2019; Wei et al., 2019).”
Near-optimal Regret Bounds for Reinforcement Learning (2008, background): “This bound holds uniformly over time and under weaker assumptions: While [7] and [11] consider only ergodic MDPs in which any policy will reach every state after a sufficient number of steps, we make only the more natural assumption of a finite diameter.”
Model-based Reinforcement Learning and the Eluder Dimension (2014, background): “We consider the reinforcement learning (RL) problem of optimizing rewards in an unknown Markov decision process (MDP) [1].”
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond (2011, unknown): “This framework was extended to multi-parameter models by Burnetas and Katehakis (1997) who showed that the number of draws up to time n , N a ( n ), of any sub-optimal arm a is lower-bounded by where KL denotes the Kullback-Leibler divergence and E ( p θ ) is the expectation under p θ ; hence, the…”
REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs (2009, background): “The problem of simultaneous estimation and control of MDPs has been studied in the control theory [Kumar and Varaiya, 1986], operations research [Burnetas and Katehakis, 1997] and machine learning communities.”
Risk versus Uncertainty in Deep Learning: Bayes, Bootstrap and the Dangers of Dropout (2016, background): “For a learning agent looking to maximize cumulative utility through time, this distinction represents a crucial dichotomy [2].”