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

48 results for “composite MDPs”

Transition Transfer

Q

-Learning for Composite Markov Decision Processesstat.ML

UCB-TQL learns from multiple tasks with shared dynamics and adapts to task-specific variations.

problem Transfer reinforcement learning with composite MDPs where tasks share core dynamics but have sparse differences.

method UCB-TQL, a novel transfer RL algorithm for composite MDPs.

result Achieved a regret bound of

ilde{O}(\sqrt{eH^5N})

that scales independently of the ambient dimension.

transfer reinforcement learning composite MDPs UCB-TQL regret bound shared dynamics

2025-02-01abs ↗pdf ↗

Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcs.LG

A new offline RL framework unifies imitation learning and vanilla offline RL.

problem Learning from expert datasets without active data collection.

method A new offline RL framework that interpolates between imitation learning and vanilla offline RL, using a weak concentrability coefficient and a lower confidence bound algorithm.

result LCB algorithm achieves a faster rate of

1/N

for nearly-expert datasets, and is adaptively optimal for the entire data composition range.

offline reinforcement learning imitation learning vanilla offline RL concentrability coefficient lower confidence bound

2021-03-22abs ↗pdf ↗

Online Learning in Kernelized Markov Decision Processescs.LG

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…

2018-05-21abs ↗pdf ↗

Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPscs.LG

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.

MDPs Regularization Policy approximation Adaptive reduction Optimization

2020-10-31abs ↗pdf ↗

Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learningstat.ML

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

O(H^{3/2}d\sqrt{K})

regret bound for Exo-MDPs, matching lower bounds.

Reinforcement Learning Markov Decision Processes Exogenous States Sample-Efficient Inventory Control

2024-09-22abs ↗pdf ↗

Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learningcs.LG

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…

2017-09-19abs ↗pdf ↗

Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcs.LG

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

Ω((H^3SA/ε^2)\log(1/δ))

sample complexity lower bound.

Reinforcement Learning MDP Non-stationary Lower Bounds PAC

2020-10-07abs ↗pdf ↗

Hierarchical Reinforcement Learning: Approximating Optimal Discounted TSP Using Local Policiescs.LG

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…

2018-03-13abs ↗pdf ↗

Solving Continual Combinatorial Selection via Deep Reinforcement Learningcs.LG

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 …

2019-09-09abs ↗pdf ↗

Optimality Guarantees for Particle Belief Approximation of POMDPscs.AI

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.

POMDPs Particle Belief Approximation MDPs Error Bounds Continuous Spaces

2022-10-10abs ↗pdf ↗

Scaling Up Robust MDPs by Reinforcement Learningcs.LG

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…

2013-06-26abs ↗pdf ↗

Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscs.LG

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.

Markov decision process sample complexity weakly communicating average-reward transient time

2024-03-18abs ↗pdf ↗

Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulationcs.LG

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…

2019-07-22abs ↗pdf ↗

Robust Markov Decision Processes without Model Estimationstat.ML

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.

Markov Decision Processes Robustness Stochastic Gradient Model-Free Oracle

2023-02-02abs ↗pdf ↗

DeepAveragers: Offline Reinforcement Learning by Solving Derived Non-Parametric MDPscs.LG

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.

offline reinforcement learning non-parametric MDPs deep representations costs performance bounds

2020-10-18abs ↗pdf ↗

Online RL in Linearly

q^π

-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 $q^π$ -realizable MDPs, simplifying to linear MDPs.

problem Online RL in episodic MDPs with linearly

q^π

-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

q^π

-realizable MDPs.

online RL Markov decision processes linearly $q^π$-realizable skip states misspecified

2023-10-11abs ↗pdf ↗

Span-Based Optimal Sample Complexity for Average Reward MDPscs.LG

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))

Markov decision process average reward sample complexity discounted MDP optimal policy

2023-11-22abs ↗pdf ↗

Efficient Planning in Large MDPs with Weak Linear Function Approximationcs.LG

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.

Markov decision processes linear approximation weak function approximation generative oracle almost-optimal actions

2020-07-13abs ↗pdf ↗

Scalable Policy-Based RL Algorithms for POMDPscs.LG

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.

Reinforcement Learning Policy Optimization TD-Learning POMDP Superstate MDP

2025-10-08abs ↗pdf ↗

Reward is enough for convex MDPscs.AI

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.

reinforcement learning Markov decision processes convex optimization Fenchel duality min-max games

2021-06-01abs ↗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 ↗

Statistical Estimation of Confounded Linear MDPs: An Instrumental Variable Approachstat.ML

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.

Markov decision process confounding instrumental variables statistical estimation linear MDPs

2022-09-12abs ↗pdf ↗

Regret Analysis in Deterministic Reinforcement Learningcs.LG

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.

regret analysis deterministic reinforcement learning logarithmic bounds graph theory MDPs

2021-06-27abs ↗pdf ↗

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPscs.AI

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

O(dH^2\barσ_T\sqrt{T})

for structured MDPs.

Reinforcement Learning Multinomial Logistic MDPs Regret Bounds Variance-Aware Logistic Bandits

2026-05-19abs ↗pdf ↗

Plannable Approximations to MDP Homomorphisms: Equivariance under Actionscs.LG

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.

action equivariance reinforcement learning latent space MDP homomorphism structured representations

2020-02-27abs ↗pdf ↗

Making Linear MDPs Practical via Contrastive Representation Learningcs.LG

New method tackles MDPs by learning normalized representations efficiently.

problem Curse of dimensionality in MDPs.

method Contrastive representation learning for linear MDPs.

result First practical method with strong theoretical guarantees and empirical performance.

Markov decision processes linear MDPs representation learning contrastive estimation sample efficiency

2022-07-14abs ↗pdf ↗

Primal-Dual Stochastic Mirror Descent for MDPsmath.OC

A new parallel algorithm for learning optimal policies in MDPs with low communication costs.

problem Learning optimal policies for infinite-horizon MDPs.

method Primal-Dual Stochastic Mirror Descent for convex programming problems with inexact constraints.

result First parallel algorithm for average-reward MDPs with generative model and low communication costs.

MDPs Stochastic Mirror Descent Convex Optimization Parallel Algorithms Generative Models

2021-02-27abs ↗pdf ↗

Algorithms for Fairness in Sequential Decision Makingcs.LG

It has recently been shown that if feedback effects of decisions are ignored, then imposing fairness constraints such as demographic parity or equality of opportunity can actually exacerbate unfairness. We propose to address this challenge by modeling feedback effects as Markov decision processes (MDPs). First, we prop…

2019-01-24abs ↗pdf ↗

MDP Homomorphic Networks: Group Symmetries in Reinforcement Learningcs.LG

The paper introduces MDP homomorphic networks for faster reinforcement learning.

problem Current reinforcement learning approaches do not exploit symmetries in the joint state-action space.

method Equivariant neural networks with group-structured symmetries (reflections, rotations).

result MDP homomorphic networks converge faster than unstructured baselines on various tasks.

reinforcement learning equivariance group symmetries neural networks CartPole

2020-06-30abs ↗pdf ↗

Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscs.LG

UCBVI-γ algorithm minimizes regret in discounted MDPs.

problem Minimizing regret in discounted MDPs.

method Optimism in the face of uncertainty principle and Bernstein-type bonus.

result UCBVI-γ achieves nearly minimax optimal regret.

reinforcement learning Markov Decision Processes discounted MDPs UCBVI-γ regret minimization

2020-10-01abs ↗pdf ↗

Exploration Bonus for Regret Minimization in Undiscounted Discrete and Continuous Markov Decision Processescs.LG

We introduce and analyse two algorithms for exploration-exploitation in discrete and continuous Markov Decision Processes (MDPs) based on exploration bonuses. SCAL $^+$ is a variant of SCAL (Fruit et al., 2018) that performs efficient exploration-exploitation in any unknown weakly-communicating MDP for which an upper bo…

2018-12-11abs ↗pdf ↗

Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearitycs.LG

New RL approach tackles non-linear MDPs without linear assumptions.

problem Sample efficiency in RL for complex, nonlinear MDPs with continuous states.

method Introduces EPW condition to relax linear structure requirements; provides sample-efficient RL algorithm.

result EPW condition allows solving MDPs without linear assumptions, including Atari games.

Reinforcement Learning Sample Efficiency Nonlinear Dynamics EPW Condition Atari Games

2021-06-15abs ↗pdf ↗

Adaptive Estimation and Optimal Control in Offline Contextual MDPs without Stationaritystat.ML

New method for estimating and optimizing MDPs without stationarity.

problem Challenges in offline contextual MDP estimation without stationarity.

method Introduces a new adaptive estimation and cost optimization approach for contextual MDPs.

result First robust, theoretically backed method for offline contextual MDP estimation.

Contextual MDPs Offline Estimation Optimal Control Non-stationarity T-Estimation

2026-05-05abs ↗pdf ↗

Efficiently Solving MDPs with Stochastic Mirror Descentcs.LG

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.

Markov decision processes stochastic mirror descent MDP solving approximation algorithms reinforcement learning

2020-08-28abs ↗pdf ↗

A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescs.LG

Optimistic PPO variant solves linear MDPs with improved regret bound.

problem Understanding theoretical limits of PPO in linear MDPs.

method Proposes an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback.

result Establishes a

ilde{\mathcal{O}}(d^{3/4}H^2K^{3/4})

regret bound.

Optimistic PPO Linear MDPs Regret Bound Reinforcement Learning Function Approximation

2023-05-15abs ↗pdf ↗

Provably Safe PAC-MDP Exploration Using Analogiescs.LG

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

problem Balancing exploration and safety in unknown MDPs with stochastic dynamics.

method Exploits analogies between state-action pairs to safely learn near-optimal policies.

result Empirically improves sample efficiency compared to existing methods.

safe exploration MDP PAC-MDP reinforcement learning sample efficiency

2020-07-07abs ↗pdf ↗

Partial Policy Iteration for L1-Robust Markov Decision Processescs.LG

New algorithms solve robust MDPs efficiently, significantly faster than existing methods.

problem Computing robust MDP solutions with uncertainty in transition probabilities is computationally expensive.

method Partial policy iteration and fast robust Bellman operator computation methods.

result The proposed methods are many orders of magnitude faster than state-of-the-art approaches.

robust MDPs partial policy iteration fast computation L1-norms quasi-linear time

2020-06-16abs ↗pdf ↗

Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcs.LG

Paper proposes an efficient RL algorithm for discounted MDPs using feature mapping.

problem Efficient reinforcement learning for large state and action spaces.

method Uses feature mapping to represent states and actions in a low-dimensional space, proposing a novel algorithm with polynomial regret bound.

result Achieves a

O(d\sqrt{T}/(1-γ)^2)

regret bound, near-optimal up to a

(1-γ)^{-0.5}

factor.

Reinforcement Learning Discounted MDPs Feature Mapping Regret Bound Polynomial Complexity

2020-06-23abs ↗pdf ↗

DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescs.LG

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

problem Non-stationary reinforcement learning in unknown change points.

method Detection Augmented Reinforcement Learning (DARLING) for tabular and linear MDPs.

result DARLING matches minimax lower bounds in tabular and linear MDPs.

reinforcement learning non-stationary dynamic regret tabular MDPs linear MDPs

2026-04-17abs ↗pdf ↗

Fast Online Exact Solutions for Deterministic MDPs with Sparse Rewardscs.LG

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…

2018-05-08abs ↗pdf ↗

Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscs.LG

Paper improves sample complexity for reward-free RL in low-rank MDPs.

problem Reward-free RL in low-rank MDPs with unknown representation and weights.

method Proposes a novel model-based algorithm RAFFLE with improved sample complexity.

result RAFFLE achieves

ε

-optimal policy and accurate system identification with significantly fewer samples.

reinforcement learning reward-free low-rank MDPs sample complexity algorithm

2023-03-20abs ↗pdf ↗

Causal Markov Decision Processes: Learning Good Interventions Efficientlystat.ML

New formalism for decision making combines causal structures with MDPs, improving reinforcement learning performance.

problem Sequential decision making with causal knowledge to improve performance.

method Causal Markov Decision Processes (C-MDPs) and C-UCBVI algorithm exploiting causal structure.

result C-UCBVI achieves an

ilde{O}(HS\sqrt{ZT})

regret bound, independent of actions.

Causal Markov Decision Processes Reinforcement Learning Sequential Decision Making Causal Structures UCBVI

2021-02-15abs ↗pdf ↗

Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescs.LG

While designing the state space of an MDP, it is common to include states that are transient or not reachable by any policy (e.g., in mountain car, the product space of speed and position contains configurations that are not physically reachable). This leads to defining weakly-communicating or multi-chain MDPs. In this…

2018-07-06abs ↗pdf ↗

Track-MDP: Reinforcement Learning for Target Tracking with Controlled Sensingeess.SP

RL approach for target tracking with unknown dynamics and sensor control.

problem Tracking an unknown target with sensor control.

method Track-MDP formulation for RL, compared with POMDP.

result Optimal RL policy tracks all target paths with certainty.

Reinforcement Learning Target Tracking Sensor Management Markov Decision Process Controlled Sensing

2024-07-19abs ↗pdf ↗

Dynamic Regret of Online Markov Decision Processescs.LG

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

problem Online MDPs with adversarial loss changes and known transitions.

method Dynamic regret measure, novel ensemble algorithms for three models.