arXiv research

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…

New rule reduces exploration regret to logarithmic, improving bad episode handling.

Algorithm reduces episode count for CMDPs with constraints.

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…

Algorithm for online decision making with unknown dynamics and aggregate feedback.

We develop algorithms with low regret for learning episodic Markov decision processes based on kernel approximation techniques. The algorithms are based on both the Upper Confidence Bound (UCB) as well as Posterior or Thompson Sampling (PSRL) philosophies, and work in the general setting of continuous state and action …

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

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

We propose a new objective function for finite-horizon episodic Markov decision processes that better captures Bellman's principle of optimality, and provide an expression for the gradient of the objective.

Study risk-sensitive reinforcement learning with Lipschitz dynamic risk measures, establishing regret bounds.

Efficient algorithm for learning from indirect feedback in complex decision-making scenarios.

New algorithm tackles constrained Markov decision processes with peak constraints.

Study minimax optimal RL in factored MDPs with bonus exploration.

We propose a new reinforcement learning algorithm for partially observable Markov decision processes (POMDP) based on spectral decomposition methods. While spectral methods have been previously employed for consistent learning of (passive) latent variable models such as hidden Markov models, POMDPs are more challenging…

StepMix algorithm ensures safe exploration in reinforcement learning with near-optimal performance.

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

New algorithm reduces regret and constraint violation in adversarial CMDP learning.

New framework for reinforcement learning with sporadic state observations.

Study evaluates policies in partially observable environments without full model specification.

New Q-learning method achieves optimal sample complexity for average-reward problems.

New RL algorithm achieves nearly optimal performance for linear MDPs.

New algorithm minimizes regret in sparse reinforcement learning.

A new method for risk-averse decision-making in Markov processes with improved regret bounds.

New framework finds periodic policies in reset-free MDPs with sublinear regret.

OPSRL algorithm reduces regret with few samples in reinforcement learning.

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

Optimistic PPO variant solves linear MDPs with improved regret bound.

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

UCBMQ improves Q-learning by adding momentum to correct bias and limit regret.

We introduce an off-policy evaluation procedure for highlighting episodes where applying a reinforcement learned (RL) policy is likely to have produced a substantially different outcome than the observed policy. In particular, we introduce a class of structural causal models (SCMs) for generating counterfactual traject…

We give a simple optimistic algorithm for which it is easy to derive regret bounds of $\tilde{O}(\sqrt{t_{\rm mix} SAT})$ after $T$ steps in uniformly ergodic Markov decision processes with $S$ states, $A$ actions, and mixing time parameter $t_{\rm mix}$. These bounds are the first regret bounds in the general, non-epi…

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

Paper bounds PAC RL sample complexity in deterministic MDPs.

New RL algorithm tackles adversarial RMAB with unknown transitions and bandit feedback.

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…

Paper proposes a method to optimize policies for diverse individuals using heterogeneous data.

Improved algorithm for misspecified MLMDPs with bounded regret and space/time complexities.

New algorithm reduces regret in CMDPs without cancellation of errors.

New algorithm learns policies without explicit rewards for MDPs.

Optimistic algorithm reduces regret in non-stationary linear MDPs.

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

We consider online learning for minimizing regret in unknown, episodic Markov decision processes (MDPs) with continuous states and actions. We develop variants of the UCRL and posterior sampling algorithms that employ nonparametric Gaussian process priors to generalize across the state and action spaces. When the trans…

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…

Most provably-efficient learning algorithms introduce optimism about poorly-understood states and actions to encourage exploration. We study an alternative approach for efficient exploration, posterior sampling for reinforcement learning (PSRL). This algorithm proceeds in repeated episodes of known duration. At the sta…

New RL algorithm for linear MDPs with nearly optimal regret.

New framework uses unsupervised learning for efficient exploration in RL.

We establish that an optimistic variant of Q-learning applied to a fixed-horizon episodic Markov decision process with an aggregated state representation incurs regret $\tilde{\mathcal{O}}(\sqrt{H^5 M K} + εHK)$, where $H$ is the horizon, $M$ is the number of aggregate states, $K$ is the number of episodes, and $ε$ is …

New method minimizes regret in AMDP with high probability.