arXiv research

Paper establishes new lower bounds for MDPs with changing transition kernels.

UCB-Advantage learns MDPs with $O(\sqrt{H^2SAT})$ regret.

We consider a reinforcement learning (RL) setting in which the agent interacts with a sequence of episodic MDPs. At the start of each episode the agent has access to some side-information or context that determines the dynamics of the MDP for that episode. Our setting is motivated by applications in healthcare where ba…

Study preference-based reinforcement learning in episodic kernel MDPs.

Efficiently identifies best policies in tabular MDPs with reduced computational cost.

We study online learning of finite Markov decision process (MDP) problems when a side information vector is available. The problem is motivated by applications such as clinical trials, recommendation systems, etc. Such applications have an episodic structure, where each episode corresponds to a patient/customer. Our ob…

New algorithms reduce dynamic regret in online MDPs with changing losses.

Study online learning in MDPs with aggregate bandit feedback, achieving low regret in both stochastic and adversarial settings.

Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-world applications, an interactive learning agent operates for a fixed or bounded period of time, for ex…

Paper bounds PAC RL sample complexity in deterministic MDPs.

New algorithm for online learning in episodic MDPs with convex objectives.

Paper optimizes learning MDPs with adversarial rewards using linear models.

Paper establishes first instance-dependent lower bound for PAC reinforcement learning.

New framework for reinforcement learning with sporadic state observations.

This is a brief technical note to clarify some of the issues with applying the application of the algorithm posterior sampling for reinforcement learning (PSRL) in environments without fixed episodes. In particular, this paper aims to: - Review some of results which have been proven for finite horizon MDPs (Osband et a…

New algorithm learns optimal policies with just 1 episode, settling horizon-dependence in RL.

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 $\tilde{O}(L|X|\sqrt{|A|T})$ regret bound, where $T$ is the number of episodes, $X$ is the state space, $A…

Quantum UCB algorithm reduces reinforcement learning regret exponentially.

A Markov Decision Process (MDP) is a popular model for reinforcement learning. However, its commonly used assumption of stationary dynamics and rewards is too stringent and fails to hold in adversarial, nonstationary, or multi-agent problems. We study an episodic setting where the parameters of an MDP can differ across…

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\wid…

Improved regret bound for MNL MDPs with variance-aware approach.

Optimistic PPO variant solves linear MDPs with improved regret bound.

Algorithm for online learning in MDPs with linear function approximation and bandit feedback.

New RL method learns K-step lookahead Q-functions for fixed-horizon MDPs.

New framework for reinforcement learning with adversarial preferences in tabular MDPs.

Algorithm reduces episode count for CMDPs with constraints.

Kernel-UCBVI algorithm balances exploration and exploitation in metric state-action spaces.

Strong worst-case performance bounds for episodic reinforcement learning exist but fortunately in practice RL algorithms perform much better than such bounds would predict. Algorithms and theory that provide strong problem-dependent bounds could help illuminate the key features of what makes a RL problem hard and reduc…

In an episodic Markov Decision Process (MDP) problem, an online algorithm chooses from a set of actions in a sequence of $H$ trials, where $H$ is the episode length, in order to maximize the total payoff of the chosen actions. Q-learning, as the most popular model-free reinforcement learning (RL) algorithm, directly pa…

Algorithm learns both stochastic and adversarial MDPs with best-of-both-worlds guarantees.

RandQL is a new model-free algorithm for MDPs with a novel learning rate randomization approach.

New RL algorithm achieves nearly optimal performance for linear MDPs.

Paper explores limits of imitation learning in MDPs, setting new suboptimality bounds.

Algorithm learns near-optimal policies for reward-mixing MDPs with few latent contexts.

Reinforcement learning (RL) has traditionally been understood from an episodic perspective; the concept of non-episodic RL, where there is no restart and therefore no reliable recovery, remains elusive. A fundamental question in non-episodic RL is how to measure the performance of a learner and derive algorithms to max…

New algorithm learns policies without explicit rewards for MDPs.

A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently, Jin et al. \cite{jin2018q} proposed a Q-learning algorithm with UCB exploration policy, and proved it has nearly optimal regret bound for finite-horizon episodic MDP. In this paper, we adapt Q-learning with…

New model selects robustly in adversarial reinforcement learning with unknown corruption.

KeRNS tackles non-stationary reinforcement learning in metric spaces.

Statistical performance bounds for reinforcement learning (RL) algorithms can be critical for high-stakes applications like healthcare. This paper introduces a new framework for theoretically measuring the performance of such algorithms called Uniform-PAC, which is a strengthening of the classical Probably Approximatel…

New method achieves nearly horizon-free offline reinforcement learning for tabular and linear MDPs.

New algorithms reduce regret in online MDPs by adapting to data and variance.

DARLING tackles non-stationary RL with guarantees, improving dynamic regret.

Efficient RL algorithm for multinomial logistic MDPs with provable guarantees.

New algorithm reduces dynamic regret for MDPs with unknown transition and adversarial rewards.

We consider the recently proposed reinforcement learning (RL) framework of Contextual Markov Decision Processes (CMDP), where the agent interacts with a (potentially adversarial) sequence of episodic tabular MDPs. In addition, a context vector determining the MDP parameters is available to the agent at the start of eac…

Improved exploration in adversarial MDPs via dilated bonuses.

New algorithm reduces reinforcement learning regret for linear MDPs with unknown transitions.