Practical reinforcement learning problems are often formulated as constrained Markov decision process (CMDP) problems, in which the agent has to maximize the expected return while satisfying a set of prescribed safety constraints. In this study, we propose a novel simulator-based method to approximately solve a CMDP pr…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,694 papers · 148 categories
Trend · papers per month
48 results for “constrained MDPs”
FMDP-BF algorithm improves RL in factored MDPs with exponential regret reduction.
problem Efficient reinforcement learning in factored MDPs with constrained RL.
method FMDP-BF algorithm leveraging factorization structure of FMDPs.
result FMDP-BF's regret is exponentially smaller than optimal algorithms for non-factored MDPs.
Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learningcs.LG
Algorithm optimizes constrained reinforcement learning with dual variables.
problem Minimizing convex functional subject to convex constraint in large state spaces.
method VPDPO algorithm using Lagrangian and Fenchel duality.
result Achieves sublinear regret and constraint violation, globally optimal policy.
New algorithm reduces sample complexity for constrained MDPs.
problem Learning policies in constrained average-reward MDPs.
method Model-based algorithm for relaxed and strict feasibility settings.
result Achieves minimax-optimal bounds for constrained MDPs.
Improved RL algorithm with linear MDPs for offline learning with partial data coverage.
problem Efficient offline RL with linear MDPs under partial data coverage.
method Primal-dual algorithm with sample complexity.
result First computationally efficient algorithm with sample complexity for offline RL with linear MDPs under partial data coverage.
New bounds for learning near-optimal policies in CMDPs with constraints.
problem Optimizing policies in CMDPs with constraints.
method Model-based algorithm addressing relaxed and strict feasibility.
result Near-optimal sample complexity bounds for CMDPs.
New algorithm solves constrained MDPs with generative model, reducing sample complexity.
problem Maximizing rewards while adhering to constraints in MDPs.
method Primal-dual framework using mirror descent value iteration.
result Near-optimal sample complexity bounds for CMDPs.
New algorithm achieves optimal regret in average reward MDPs without prior bias information.
problem Achieving optimal regret in average reward MDPs with computational efficiency and without prior bias information.
method Projective Mitigated Extended Value Iteration (PMEVI) to compute bias-constrained optimal policies efficiently.
result First tractable algorithm with minimax optimal regret of .
Reward suffices for convex MDPs, expanding RL to new problems.
problem Capturing goals as convex functions of stationary distribution.
method Reformulated as a min-max game using Fenchel duality.
result Convex MDPs require non-stationary reward functions.
Improved regret bound for MNL MDPs with variance-aware approach.
problem Optimal reinforcement learning for MNL MDPs with structured variance.
method Introducing a problem-dependent constant measuring average variance, proposing an algorithm with improved regret bound.
result Minimax optimal regret bound of for structured MDPs.
New algorithm reduces sample complexity for safe reinforcement learning.
problem Safe reinforcement learning in constrained MDPs with performance and safety constraints.
method Model-based primal-dual algorithm balancing regret and bounded constraint violations.
result Proves near-optimal policies with bounded violations or zero violations in CMDPs.
Unified framework for solving MDPs with stochastic mirror descent.
problem Approximately solving infinite-horizon Markov decision processes (MDPs).
method Primal-dual stochastic mirror descent for MDPs with a unified framework.
result Computes ε-optimal policies with expected samples for both average-reward and discounted MDPs.
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…
We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound on the span of the optimal bias function is known. For an MDP with states, actions and possible next states, we prove a …
In order to satisfy safety conditions, an agent may be constrained from acting freely. A safe controller can be designed a priori if an environment is well understood, but not when learning is employed. In particular, reinforcement learned (RL) controllers require exploration, which can be hazardous in safety critical …
CPPO learns policies from partial offline data in MDPs with structural assumptions.
problem Offline Reinforcement Learning with partial coverage assumption.
method Constrained Pessimistic Policy Optimization (CPPO) using a function class and model class constraint.
result CPPO achieves PAC guarantee with partial coverage, learning competitive policies.
Batch Reinforcement Learning (Batch RL) consists in training a policy using trajectories collected with another policy, called the behavioural policy. Safe policy improvement (SPI) provides guarantees with high probability that the trained policy performs better than the behavioural policy, also called baseline in this…
Paper tackles robust MDPs with sample complexity guarantees.
problem Learning safe policies in uncertain environments.
method Introduces augmented state space and RCVI algorithm.
result First sample complexity guarantee for RCMDPs.
Paper proposes a model-free algorithm for CMDPs with long-term constraints, achieving optimal regret bounds.
problem Optimizing systems with long-term constraints where transition probabilities are unknown.
method Combines concepts from constrained optimization and Q-learning to propose an algorithm.
result Achieves optimal regret bounds for reward and constraint violation.
Survey of mathematical foundations for reinforcement learning.
problem Design and analysis of modern reinforcement learning algorithms.
method Organizes mathematical structures from probability, optimization, and operator theory.
result Unified mathematical entry point for researchers in various fields.
Paper explores limits of imitation learning in MDPs, setting new suboptimality bounds.
problem Understanding the statistical limits of imitation learning in MDPs.
method Analyzes minimax statistical limits in two settings: pre-interaction and interaction.
result Establishes suboptimality bounds for imitation learning in MDPs, showing improvements with knowledge of transition.
Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscs.LG
Study examines sample complexity for RL with safety constraints.
problem Ensuring safety in RL for systems with constraints.
method Analyzes two RL approaches: generative and online.
result Sample complexity increased by a logarithmic factor in constraints.
The paper analyzes CMDPs, balancing exploration and exploitation to avoid constraint violations.
problem Balancing exploration and exploitation in CMDPs to satisfy constraints.
method Two approaches: optimistic planning and incremental updates of primal and dual variables.
result Both approaches achieve sublinear regret on utility and constraint violations, with stronger guarantees for the linear programming approach.
Proposes Constrained Q-learning for reinforcement learning with constraints.
problem Optimizing multiple objectives while adhering to constraints in reinforcement learning.
method Directly restricts the action space in Q-update to learn optimal Q-function for constrained MDP.
result Improves safety and optimality in high-level decision making for autonomous driving.
Adaptive reduction scheme approximates optimal policy in regularized MDPs.
problem Finding near optimal policy in regularized MDPs with biased solutions.
method Adaptive reduction of regularization parameter λ to approximate optimal policy.
result Iteration complexity reduced for obtaining ε-optimal policy.
We study Exo-MDPs to reduce sample complexity in reinforcement learning.
problem Reducing sample complexity in reinforcement learning for structured MDPs.
method Introducing Exo-MDPs and proving structural equivalence to linear mixture MDPs, establishing regret bounds.
result Proved regret bound for Exo-MDPs, matching lower bounds.
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…
Paper establishes new lower bounds for MDPs with changing transition kernels.
problem Minimizing sample complexity and regret in non-stationary MDPs.
method Developed novel lower bounds and constructed hard MDPs.
result Proved sample complexity lower bound.
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 …
New algorithms speed up inverse reinforcement learning by solving MDPs once.
problem Slow convergence in Maximum Entropy Inverse Reinforcement Learning.
method Deep Inverse Q-learning with constraints exploiting Q-learning.
result Up to several orders of magnitude speedup compared to existing methods.
New method approximates POMDPs with PB-MDPs, providing error bounds and practical algorithms.
problem Difficulty in solving POMDPs with continuous or hybrid state and observation spaces.
method Bounding particle filtering error and adapting MDP algorithms to POMDPs.
result General theory and practical algorithms for POMDPs with no direct dependence on state and observation space sizes.
We consider large-scale Markov decision processes (MDPs) with parameter uncertainty, under the robust MDP paradigm. Previous studies showed that robust MDPs, based on a minimax approach to handle uncertainty, can be solved using dynamic programming for small to medium sized problems. However, due to the "curse of dimen…
Optimizes learning policies in MDPs with weakly communicating structure.
problem Learning optimal policies in weakly communicating MDPs with generative model.
method Span-based approach, reducing to discounted MDPs for analysis.
result First minimax optimal sample complexity bound for weakly communicating MDPs.
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…
New method removes oracle and reduces memory usage for robust MDPs.
problem Applying robust MDPs in practice due to model estimation and oracle requirements.
method Transformed robust MDPs into an alternative form allowing stochastic gradient methods and model-free approach.
result Sample-efficient algorithm with lower storage requirement and no oracle.
DeepAveragers solves offline RL by solving derived MDPs from static data.
problem Offline reinforcement learning with limited data.
method Solves derived non-parametric MDPs (DAC-MDPs) using deep representations and costs for under-represented parts.
result The approach can lower-bound performance and scale to complex offline RL problems.
Online RL in Linearly -Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignorecs.LG
New RL method learns to skip states in linearly -realizable MDPs, simplifying to linear MDPs.
problem Online RL in episodic MDPs with linearly -realizable action-values.
method Derives a novel algorithm that learns to skip states and applies a linear MDP algorithm.
result First polynomial-sample-complexity online RL algorithm for linearly -realizable MDPs.
We study a risk-constrained version of the stochastic shortest path (SSP) problem, where the risk measure considered is Conditional Value-at-Risk (CVaR). We propose two algorithms that obtain a locally risk-optimal policy by employing four tools: stochastic approximation, mini batches, policy gradients and importance s…
Optimizes learning policies in average-reward MDPs with improved sample complexity.
problem Learning optimal policies in average-reward MDPs with limited samples.
method Reduces to discounted MDPs and uses improved bounds for variance parameters.
result Establishes minimax optimal sample complexity bound of O(SA(H/ε^2))
New algorithm for reinforcement learning in uncertain environments with unknown thresholds.
problem Safety in reinforcement learning in unknown and uncertain environments.
method Growing-Window estimator sampling and Stochastic Pessimistic-Optimistic Thresholding (SPOT) algorithm.
result Achieves sublinear regret and constraint violation of .
Efficiently plans large MDPs with weak function approximations.
problem Planning in large MDPs with limited function approximation capabilities.
method Uses linear value function approximation with weak requirements and a generative oracle.
result Produces almost-optimal actions for any state with polynomial computation time.
We solve POMDPs by approximating them as finite-state MDPs.
problem Computational challenges in learning optimal policies for POMDPs.
method Transform POMDP into a Superstate MDP, apply TD-learning and policy optimization.
result Finite-time bounds on TD-learning error for non-Markovian dynamics.
New algorithm reduces suboptimality in imitation learning to nearly optimal levels.
problem Statistical limits of imitation learning in MDPs with known transitions.
method Mimic-MD algorithm and reduction to value estimation problem.
result Upper bound of for suboptimality, with efficient computation.
New algorithm achieves sublinear regret in CMDPs without error cancellations.
problem Safety constraints in reinforcement learning with error cancellations.
method Model-based primal-dual algorithm for CMDPs with multiple constraints.
result Achieves sublinear regret without error cancellations.
The paper addresses statistical estimation in MDPs with confounders using instrumental variables.
problem Statistical estimation of value functions in MDPs with unobservable confounders.
method Two-stage estimator based on instrumental variables for confounded linear MDPs.
result Established statistical properties of the two-stage estimator, including error bounds and asymptotic normality.
New algorithm tackles constrained Markov decision processes with peak constraints.
problem Optimizing dynamic systems with peak constraints.
method Model-free algorithm converting PCMDP to unconstrained problem, applying Q-learning.
result Algorithm achieves -PAC policy under certain conditions.
Study on regret minimization in deterministic MDPs.
problem Minimizing regret in deterministic reinforcement learning.
method Logarithmic regret lower bounds, leveraging graph theory and cycles.
result Explicitly quantifies the fundamental limit of performance achievable by any learning algorithm.
This work uses action equivariance to learn structured latent spaces for reinforcement learning.
problem Learning structured latent spaces for reinforcement learning.
method Introduced a contrastive loss function to enforce action equivariance on learned representations.
result Optimal policies in the abstract MDP can be successfully lifted to the original MDP.