arXiv research

Study on regret minimization in deterministic MDPs.

Paper bounds PAC RL sample complexity in deterministic MDPs.

We consider deterministic Markov decision processes (MDPs) and apply max-plus algebra tools to approximate the value iteration algorithm by a smaller-dimensional iteration based on a representation on dictionaries of value functions. The setup naturally leads to novel theoretical results which are simply formulated due…

This work exploits action equivariance for representation learning in reinforcement learning. Equivariance under actions states that transitions in the input space are mirrored by equivalent transitions in latent space, while the map and transition functions should also commute. We introduce a contrastive loss function…

New method finds exact Pareto front for MO-MDPs efficiently.

New algorithms reduce regret in both stochastic and deterministic environments.

We present new algorithms for computing and approximating bisimulation metrics in Markov Decision Processes (MDPs). Bisimulation metrics are an elegant formalism that capture behavioral equivalence between states and provide strong theoretical guarantees on differences in optimal behaviour. Unfortunately, their computa…

Markov Decision Processes (MDPs) are a mathematical framework for modeling sequential decision making under uncertainty. The classical approaches for solving MDPs are well known and have been widely studied, some of which rely on approximation techniques to solve MDPs with large state space and/or action space. However…

In this paper we consider the basic version of Reinforcement Learning (RL) that involves computing optimal data driven (adaptive) policies for Markovian decision process with unknown transition probabilities. We provide a brief survey of the state of the art of the area and we compare the performance of the classic UCB…

We study Exo-MDPs to reduce sample complexity in reinforcement learning.

We propose an algorithm for deterministic continuous Markov Decision Processes with sparse rewards that computes the optimal policy exactly with no dependency on the size of the state space. The algorithm has time complexity of $O( |R|^3 \times |A|^2 )$ and memory complexity of $O( |R| \times |A| )$, where $|R|$ is the…

In this paper we derive an efficient method for computing the indices associated with an asymptotically optimal upper confidence bound algorithm (MDP-UCB) of Burnetas and Katehakis (1997) that only requires solving a system of two non-linear equations with two unknowns, irrespective of the cardinality of the state spac…

We study a reinforcement learning setting, where the state transition function is a convex combination of a stochastic continuous function and a deterministic function. Such a setting generalizes the widely-studied stochastic state transition setting, namely the setting of deterministic policy gradient (DPG). We firstl…

ASE safely explores unknown MDPs with unknown dynamics, improving sample efficiency.

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

We propose a method for efficient training of Q-functions for continuous-state Markov Decision Processes (MDPs) such that the traces of the resulting policies satisfy a given Linear Temporal Logic (LTL) property. LTL, a modal logic, can express a wide range of time-dependent logical properties (including "safety") that…

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

Lower bounds for PI on multi-action MDPs are established, showing complexity grows with action count.

We propose an actor-critic, model-free, and online Reinforcement Learning (RL) framework for continuous-state continuous-action Markov Decision Processes (MDPs) when the reward is highly sparse but encompasses a high-level temporal structure. We represent this temporal structure by a finite-state machine and construct …

In this work, we provide theoretical guarantees for reward decomposition in deterministic MDPs. Reward decomposition is a special case of Hierarchical Reinforcement Learning, that allows one to learn many policies in parallel and combine them into a composite solution. Our approach builds on mapping this problem into a…

TensorPlan algorithm finds δ-optimal policies with poly$(H,d)$ queries under linearly realizable state-value function.

New algorithm reduces regret for linear bandits with unknown noise variance.

Reinforcement Learning (RL) has emerged as an efficient method of choice for solving complex sequential decision making problems in automatic control, computer science, economics, and biology. In this paper we present a model-free RL algorithm to synthesize control policies that maximize the probability of satisfying h…

We provide the first solution for model-free reinforcement learning of ω-regular objectives for Markov decision processes (MDPs). We present a constructive reduction from the almost-sure satisfaction of ω-regular objectives to an almost- sure reachability problem and extend this technique to learning how to control an …

Paper analyzes online reinforcement learning with outcome-based feedback, providing efficient algorithms and fundamental limits.

We present a method for a certain class of Markov Decision Processes (MDPs) that can relate the optimal policy back to one or more reward sources in the environment. For a given initial state, without fully computing the value function, q-value function, or the optimal policy the algorithm can determine which rewards w…

New complexity measure helps in agnostic reinforcement learning with or without access to MDP dynamics.

New lower bound shows RL with linear approximations is computationally hard.

Many problems in sequential decision making and stochastic control often have natural multiscale structure: sub-tasks are assembled together to accomplish complex goals. Systematically inferring and leveraging hierarchical structure, particularly beyond a single level of abstraction, has remained a longstanding challen…

Study non-asymptotic BPI guarantees for online RL.

A quantum reinforcement learning algorithm reduces sample complexity.

New RL theory predicts deep RL success based on greedy actions under random policies.

Paper develops methods to optimize policies directly from human feedback without reward inference.

TensorPlan shows an exponential lower bound for planning in MDPs with linearly realizable value functions.

MVPI framework optimizes risk in reinforcement learning, improving performance in robot simulations.

Efficient RL algorithm for MDPs with linear $Q^π$ realizability, achieving optimal regret bound.

Bayesian framework for learning optimal action-value function in MDPs.

Reinforcement Learning (RL) is a widely employed machine learning architecture that has been applied to a variety of control problems. However, applications in safety-critical domains require a systematic and formal approach to specifying requirements as tasks or goals. We propose a model-free RL algorithm that enables…

ETGL-DDPG improves DDPG for sparse reward control with new exploration and replay techniques.

New algorithm reduces regret in infinite MDPs with optimal variance-dependent bounds.

Adaptive reduction scheme approximates optimal policy in regularized MDPs.

In this paper, a sparse Markov decision process (MDP) with novel causal sparse Tsallis entropy regularization is proposed.The proposed policy regularization induces a sparse and multi-modal optimal policy distribution of a sparse MDP. The full mathematical analysis of the proposed sparse MDP is provided.We first analyz…

The paper introduces an adjacency constraint to improve goal-conditioned HRL.

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

We consider the Markov Decision Process (MDP) of selecting a subset of items at each step, termed the Select-MDP (S-MDP). The large state and action spaces of S-MDPs make them intractable to solve with typical reinforcement learning (RL) algorithms especially when the number of items is huge. In this paper, we present …

A simple and natural algorithm for reinforcement learning (RL) is Monte Carlo Exploring Starts (MCES), where the Q-function is estimated by averaging the Monte Carlo returns, and the policy is improved by choosing actions that maximize the current estimate of the Q-function. Exploration is performed by "exploring start…

Applying probabilistic models to reinforcement learning (RL) enables the application of powerful optimisation tools such as variational inference to RL. However, existing inference frameworks and their algorithms pose significant challenges for learning optimal policies, e.g., the absence of mode capturing behaviour in…

New algorithm reduces suboptimality in imitation learning to nearly optimal levels.