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,695 papers · 148 categories

Trend · papers per month

count % of corpus

41 results for “CMDP”

Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcs.LG

Efficient algorithm for CMDPs reduces to offline density estimation.

problem Offline learning for CMDPs with horizon H.

method Reduction to offline density estimation, layerwise exploration-exploitation tradeoff.

result First efficient and near-optimal reduction from CMDPs to offline density estimation.

CMDP offline learning density estimation reinforcement learning layerwise structure

2024-05-28abs ↗pdf ↗

Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescs.LG

New algorithm reduces regret in CMDPs without cancellation of errors.

problem Lagrangian approaches in CMDPs struggle with cancellation of errors.

method OptAug-CMDP, based on augmented Lagrangian method.

result Regret of

ilde{O}(\sqrt{K})

for both objective and constraint violation.

CMDPs Lagrangian Regret Augmented Lagrangian Constraint Violation

2023-06-12abs ↗pdf ↗

Exploration-Exploitation in Constrained MDPscs.LG

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.

CMDPs exploration-exploitation constraint satisfaction optimistic planning dual formulation

2020-03-04abs ↗pdf ↗

A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcs.LG

Paper tackles offline CMDP problems with near-optimal algorithm and sample complexity bound.

problem Offline CMDP problems with only offline data available.

method DPDL algorithm using single-policy concentrability coefficient

C^*

and deviation control mechanism.

result DPDL algorithm matches sample complexity lower bound with

ilde{\mathcal{O}}((1-γ)^{-1})

factor.

CMDP Offline Learning Primal-Dual Method Concentrability Coefficient Deviation Control

2022-07-13abs ↗pdf ↗

Truly No-Regret Learning in Constrained MDPscs.LG

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.

CMDPs Primal-dual Sublinear regret Safety constraints Reinforcement learning

2024-02-24abs ↗pdf ↗

Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcs.AI

Constrained Markov Decision Process (CMDP) is a natural framework for reinforcement learning tasks with safety constraints, where agents learn a policy that maximizes the long-term reward while satisfying the constraints on the long-term cost. A canonical approach for solving CMDPs is the primal-dual method which updat…

2018-02-19abs ↗pdf ↗

Sample Complexity Characterization for Linear Contextual MDPscs.LG

Paper studies linear CMDPs, improving sample complexity for both models.

problem Improving sample complexity for linear CMDPs.

method Proposes novel model-based algorithms for two linear function approximation models.

result Guaranteed ε-suboptimality gap with desired polynomial sample complexity.

reinforcement learning contextual MDPs linear function approximation sample complexity

2024-02-05abs ↗pdf ↗

Reconnaissance and Planning algorithm for constrained MDPcs.LG

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…

2019-09-20abs ↗pdf ↗

Near-Optimal Sample Complexity Bounds for Constrained MDPscs.LG

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.

Markov decision processes constrained MDPs sample complexity slater constant policy optimization

2022-06-13abs ↗pdf ↗

A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscs.LG

Algorithm reduces episode count for CMDPs with constraints.

problem Online decision-making with constraints in episodic CMDPs.

method Optimistic planning using linear programming for PAC guarantee.

result Probably approximately correct (PAC) guarantee on episode count.

Markov Decision Processes Constrained Optimization Linear Programming Online Algorithms PAC Guarantees

2020-09-23abs ↗pdf ↗

Sample Complexity Bounds for Linear Constrained MDPs with a Generative Modelcs.LG

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.

Markov decision processes constrained optimization sample complexity generative model mirror descent

2025-07-02abs ↗pdf ↗

Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscs.LG

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

problem Online learning for episodic stochastically constrained Markov decision processes (CMDPs) with adversarial loss.

method Upper Confidence Primal-Dual Reinforcement Learning (UC-PDL) algorithm.

result Achieves

\widetilde{\mathcal{O}}(L|\mathcal{S}|\sqrt{|\mathcal{A}|T})

upper bounds of both regret and constraint violation.

Reinforcement Learning CMDP Adversarial Loss Upper Confidence Primal-Dual

2020-03-02abs ↗pdf ↗

Deep reinforcement learning under signal temporal logic constraints using Lagrangian relaxationstat.ML

Study uses DRL with Lagrangian relaxation to solve temporal control tasks with STL constraints.

problem Optimal control problems with temporal logic constraints.

method Extended CMDP formulation, Lagrangian relaxation, two-phase constrained DRL algorithm.

result Demonstrated learning performance of the proposed algorithm through simulations.

Deep reinforcement learning Temporal logic constraints Lagrangian relaxation Optimal control Markov decision process

2022-01-21abs ↗pdf ↗

OSIL: Learning Offline Safe Imitation Policies with Safety Inferred from Non-preferred Trajectoriescs.LG

OSIL learns safe policies from unsafe demonstrations.

problem Offline safe imitation learning with implicit safety.

method Formulates CMDP, infers safety from non-preferred trajectories, learns cost model.

result OSIL learns safer policies without degrading reward performance.

offline imitation learning safe policy CMDP non-preferred trajectories cost model

2026-02-11abs ↗pdf ↗

A Gradient-Aware Search Algorithm for Constrained Markov Decision Processescs.LG

A new algorithm finds optimal solutions for constrained decision processes.

problem Optimizing state-value functions with constraints in CMDPs.

method Gradient-Aware Search (GAS) exploiting PWLC structure.

result GAS converges faster and more reliably than existing methods.

Gradient-Aware Search Constrained Markov Decision Processes Piece-wise Linear Convex Optimization Robot Navigation

2020-05-07abs ↗pdf ↗

Model-Free Algorithm and Regret Analysis for MDPs with Long-Term Constraintscs.LG

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.

Markov Decision Process Constrained Optimization Q-learning Long-term Constraints Regret Analysis

2020-06-10abs ↗pdf ↗

Contextual Markov Decision Processesstat.ML

We consider a planning problem where the dynamics and rewards of the environment depend on a hidden static parameter referred to as the context. The objective is to learn a strategy that maximizes the accumulated reward across all contexts. The new model, called Contextual Markov Decision Process (CMDP), can model a cu…

2015-02-08abs ↗pdf ↗

Near-Optimal Sample Complexity for Online Constrained MDPscs.LG

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.

reinforcement learning Markov decision processes online learning constrained optimization slater constant

2026-02-16abs ↗pdf ↗

Learning in Markov Decision Processes under Constraintscs.LG

UCRL-CMDP algorithm optimizes RL with constraints on average costs.

problem Optimizing RL in MDPs with average cost constraints.

method Model-based RL algorithms maximizing reward while keeping costs within bounds.

result UCRL-CMDP algorithm's expected regret is upper-bounded by $T^{2\slash 3}$.

reinforcement learning Markov decision processes average cost constraints UCRL-CMDP regret analysis

2020-02-27abs ↗pdf ↗

AACC: Asymmetric Actor-Critic in Contextual Reinforcement Learningcs.LG

AACC improves RL performance in changing environments.

problem Deterioration of RL performance in real-world tasks.

method Formalizes CMDPs, proposes AACC for contextual RL.

result AACC outperforms baselines in various simulated environments.

Reinforcement Learning Contextual RL CMDPs Actor-Critic Generalization

2022-08-03abs ↗pdf ↗

Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcs.LG

New algorithm optimizes reward while ensuring safety in complex decision-making problems.

problem Maximizing reward while adhering to safety constraints in complex decision-making problems.

method Optimistic Primal-Dual Proximal Policy Optimization (OPDOP) algorithm combining least-squares policy evaluation and a bonus term for safe exploration.

result Achieves

ilde{O}(d H^{2.5}\sqrt{T})

regret and

ilde{O}(d H^{2.5}\sqrt{T})

constraint violation.

Safe Reinforcement Learning CMDP Optimization Proximal Policy Optimization Function Approximation

2020-03-01abs ↗pdf ↗

A Nonmyopic Approach to Cost-Constrained Bayesian Optimizationcs.LG

New method optimizes costly evaluations in Bayesian optimization.

problem Costly evaluations in BO methods, especially in hyperparameter tuning.

method Formulated as a CMDP, developed rollout approximation for optimal policy.

result Improved cost efficiency over standard BO methods.

Bayesian optimization Cost-constrained Markov decision process Hyperparameter tuning Sensor selection

2021-06-10abs ↗pdf ↗

A Lyapunov-based Approach to Safe Reinforcement Learningcs.LG

In many real-world reinforcement learning (RL) problems, besides optimizing the main objective function, an agent must concurrently avoid violating a number of constraints. In particular, besides optimizing performance it is crucial to guarantee the safety of an agent during training as well as deployment (e.g. a robot…

2018-05-20abs ↗pdf ↗

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.

Reinforcement Learning Safety Constraints Sample Complexity Constrained Markov Decision Process PAC Learning

2020-08-01abs ↗pdf ↗

Discovering Diverse Nearly Optimal Policies with Successor Featurescs.AI

Proposes method to discover diverse near-optimal policies in reinforcement learning.

problem Finding different solutions to the same problem in reinforcement learning.

method Formalizes problem as CMDP, uses Successor Features, proposes new diversity rewards.

result Proposed method discovers diverse near-optimal policies that are robust and distinct.

reinforcement learning diverse policies successor features CMDP diversity rewards

2021-06-01abs ↗pdf ↗

Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learningcs.LG

Develops new reinforcement learning methods for complex constrained decision-making problems.

problem Complex constrained decision-making problems with a continuum of constraints.

method Proposes semi-infinitely constrained Markov decision processes (SICMDPs) and two reinforcement learning algorithms: SI-CRL and SI-CPO.

result Demonstrates the effectiveness of SI-CRL and SI-CPO in solving complex sequential decision-making tasks.

Reinforcement Learning Markov Decision Processes Constrained Optimization Semi-Infinitely Programming Deep Reinforcement Learning

2023-04-29abs ↗pdf ↗

Lyapunov-based uncertainty-aware safe reinforcement learningcs.LG

A new RL model ensures safe learning in uncertain environments.

problem Safe reinforcement learning in uncertain, partially observable environments.

method Lyapunov-based uncertainty quantification and Transformers for memory.

result Significant improvement in safety and optimality in grid-world tasks.

Reinforcement Learning Safety Constraints Lyapunov Function Uncertainty Quantification Transformers

2021-07-29abs ↗pdf ↗

No-regret Exploration in Contextual Reinforcement Learningcs.LG

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…

2019-03-14abs ↗pdf ↗

Safe Wasserstein Constrained Deep Q-Learningcs.LG

SafeQ-Learning uses Wasserstein DRO to ensure safety in online learning.

problem Ensuring safety in online Q-Learning algorithms.

method DrQ algorithm that uses Wasserstein ambiguity sets and offset variables.

result SafeQ-Learning provides idealistic probabilistic safety guarantees.

Wasserstein DRO Q-Learning Safety guarantees Online learning Markov decision process

2020-02-07abs ↗pdf ↗

Markov Decision Processes with Continuous Side Informationstat.ML

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…

2017-11-15abs ↗pdf ↗

Constrained Combinatorial Optimization with Reinforcement Learningcs.LG

Paper uses RL to solve constrained combinatorial optimization problems.

problem Constrained combinatorial optimization problems.

method Extending NCO theory to CMDPs, using RL with penalty signals.

result Proposes a superior method for solving constrained problems.

Reinforcement Learning Combinatorial Optimization Constraint Satisfaction Markov Decision Processes Job Shop Problem

2020-06-22abs ↗pdf ↗

Learning Safety Constraints from Demonstrations with Unknown Rewardscs.LG

CoCoRL learns safe constraints from demonstrations with unknown rewards.

problem Learning safe constraints from demonstrations with different unknown rewards.

method Convex Constraint Learning for Reinforcement Learning (CoCoRL) constructs a convex safe set based on demonstrations.

result CoCoRL learns constraints that lead to safe driving behavior and can safely transfer to different tasks and environments.

Reinforcement Learning Safe Driving Constraint Learning Unknown Rewards Convex Optimization

2023-05-25abs ↗pdf ↗

Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholdscs.LG

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

ilde{\mathcal{O}}(\sqrt{T})

reinforcement learning Markov decision processes uncertain environments thresholds safety

2025-04-07abs ↗pdf ↗

Mathematical methods of reinforcement learningmath.OC

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.

reinforcement learning Markov decision processes Bellman operators stochastic approximation convex duality

2026-07-08abs ↗pdf ↗

ClauseLens: Clause-Grounded, CVaR-Constrained Reinforcement Learning for Trustworthy Reinsurance Pricingcs.LG

ClauseLens uses reinforcement learning to price reinsurance treaties transparently and auditably.

problem Opaque and difficult-to-audit reinsurance treaty pricing practices.

method ClauseLens models treaty pricing as a Risk-Aware Constrained Markov Decision Process (RA-CMDP), incorporating legal clauses and generating interpretable explanations.

result ClauseLens reduces solvency violations and improves tail-risk performance, achieving 88.2% accuracy in clause-grounded explanations.

reinforcement learning reinsurance treaty pricing legal clauses interpretability

2025-10-09abs ↗pdf ↗

Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewardscs.LG

The paper develops a reinforcement learning model to estimate ad impact considering delayed and cumulative effects.

problem Accurately estimating ad impact considering delayed and long-term effects, cumulative impacts, and customer heterogeneity.

method Modeling ad bidding as a Contextual Markov Decision Process (CMDP) with delayed Poisson rewards, proposing a two-stage maximum likelihood estimator and reinforcement learning algorithm.

result Achieves a near-optimal regret bound of

\tilde{O}{(dH^2\sqrt{T})}

, validating the approach through simulation experiments.

reinforcement learning ad impact estimation delayed rewards customer heterogeneity contextual Markov decision process

2025-10-22abs ↗pdf ↗

FedSGM: A Unified Framework for Constraint Aware, Bidirectionally Compressed, Multi-Step Federated Optimizationcs.LG

FedSGM tackles constrained federated learning with unified framework.

problem Functional constraints, communication bottlenecks, local updates, and partial client participation in federated learning.

method Unified framework based on switching gradient method, incorporating bi-directional error feedback, and soft switching for stability.

result Achieves

\boldsymbol{\mathcal{O}}(1/\sqrt{T})

convergence rate with high-probability bounds decoupling from sampling noise.

federated learning constraint optimization bi-directional feedback soft switching convergence guarantees

2026-01-23abs ↗pdf ↗

Provably Efficient Sample Complexity for Robust CMDPcs.LG

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.

Robust MDP Sample Complexity Policy Optimization Value Iteration Safety Constraints

2025-11-10abs ↗pdf ↗

Contextual Bilevel Reinforcement Learning for Incentive Alignmentmath.OC

CB-RL solves complex decision-making problems with contextual information and exogenous events.

problem Optimal policy in strategic decision-making problems that depend on environmental configuration and exogenous events.

method Contextual Bilevel Reinforcement Learning (CB-RL) with a stochastic Hyper Policy Gradient Descent (HPGD) algorithm.

result Demonstrated convergence and performance of the HPGD algorithm for reward shaping and tax design.

Reinforcement Learning Bilevel Optimization Stackelberg Game Hypergradient Contextual Markov Decision Process

2024-06-03abs ↗pdf ↗

Provably Efficient Model-Free Algorithm for MDPs with Peak Constraintsmath.OC

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

(ε,p)

-PAC policy under certain conditions.

Markov Decision Process Peak Constraints Q-learning PAC Policy Dynamic Systems

2020-03-11abs ↗pdf ↗

Lyapunov-based Safe Policy Optimization for Continuous Controlcs.LG

We study continuous action reinforcement learning problems in which it is crucial that the agent interacts with the environment only through safe policies, i.e.,~policies that do not take the agent to undesirable situations. We formulate these problems as constrained Markov decision processes (CMDPs) and present safe p…

2019-01-28abs ↗pdf ↗