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

Trend · papers per month

count % of corpus

48 results for “episodic Markov decision process”

Online Convex Optimization in Adversarial Markov Decision Processescs.LG

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…

2019-05-19abs ↗pdf ↗

Logarithmic Regret of Exploration in Average Reward Markov Decision Processescs.LG

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

problem Improving exploration regret in average reward MDPs.

method Replacing Doubling Trick with Vanishing Multiplicative rule in EVI-based algorithms.

result Regret is logarithmic under the new rule, significantly better than linear.

regret minimization Markov decision processes exploration confidence regions Doubling Trick

2025-02-10abs ↗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 ↗

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 ↗

Online Markov Decision Processes with Aggregate Bandit Feedbackcs.LG

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

problem Online decision making with unknown dynamics and aggregate bandit feedback.

method Developed an algorithm based on online mirror descent with a self-concordant barrier regularization and an increasing learning rate schedule.

result Achieved

O(\sqrt{K})

regret for the online Markov Decision Process with

K

episodes.

Online Markov Decision Processes Aggregate Bandit Feedback Adversarial Dynamics Online Mirror Descent Self-Concordant Barrier

2021-01-31abs ↗pdf ↗

On Online Learning in Kernelized Markov Decision Processescs.LG

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 …

2019-11-04abs ↗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.

result Provably optimal dynamic regret bounds for episodic SSP, improved bounds for predictable environments.

online MDPs dynamic regret ensemble algorithms adversarial changes predictable environments

2022-08-26abs ↗pdf ↗

Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processescs.LG

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

problem Identifying the best policy in tabular MDPs with high computational cost.

method Combines posterior sampling with online learning to achieve asymptotic optimality.

result Achieves optimal sample complexity and posterior contraction rate with

O(S^2AH)

per episode.

policy identification Markov decision processes posterior sampling online learning tabular MDPs

2026-05-05abs ↗pdf ↗

Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measurescs.LG

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

problem Risk-sensitive reinforcement learning in Markov decision processes.

method Two model-based algorithms for Lipschitz dynamic risk measures, focusing on regret bounds.

result Upper bounds demonstrate optimal dependencies on actions and episodes, reflecting risk sensitivity vs. sample complexity trade-off.

reinforcement learning risk sensitivity dynamic risk measures regret bounds Markov decision processes

2023-06-04abs ↗pdf ↗

Classical Policy Gradient: Preserving Bellman's Principle of Optimalitycs.LG

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.

2019-06-06abs ↗pdf ↗

Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedbackcs.LG

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

problem Learning from indirect feedback in realistic scenarios with personalized mechanisms.

method IGW algorithm for policy optimization, extending reward-estimator construction from single-step to multi-step.

result Achieves sublinear regret guarantee for contextual episodic MDPs with personalized feedback.

Markov Decision Processes Personalized Feedback Inverse-Gap-Weighting Efficient Algorithms Sublinear Regret

2026-02-09abs ↗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 ↗

Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processescs.LG

Study minimax optimal RL in factored MDPs with bonus exploration.

problem Optimal reinforcement learning in episodic factored MDPs.

method Proposes two model-based algorithms with bonus exploration for minimax optimal regret.

result Achieves minimax optimal regret guarantees for rich factored structures.

Reinforcement Learning Factored Markov Decision Processes Bonus Exploration Minimax Optimal

2020-06-24abs ↗pdf ↗

Reinforcement Learning of POMDPs using Spectral Methodscs.AI

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…

2016-02-25abs ↗pdf ↗

Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscs.LG

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

problem Conservative exploration in reinforcement learning under episode-wise constraints.

method StepMix algorithm balances exploitation and exploration while ensuring episode-wise conservative constraint.

result StepMix achieves near-optimal regret order as in the constraint-free setting.

reinforcement learning conservative exploration regret Markov Decision Process episodic

2023-06-09abs ↗pdf ↗

Online Episodic Convex Reinforcement Learningcs.LG

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

problem Online episodic convex reinforcement learning.

method Online mirror descent algorithm with varying constraint sets and exploration bonus.

result Near-optimal regret bounds for online CURL without prior knowledge of transition function.

online learning reinforcement learning convex optimization mirror descent regret bounds

2025-05-12abs ↗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 ↗

Provably Efficient Reinforcement Learning with Aggregated Statesstat.ML

Optimized Q-learning reduces regret in state-aggregated MDPs.

problem Reducing regret in reinforcement learning with state aggregation.

method Optimistic Q-learning applied to fixed-horizon episodic MDPs with aggregated states.

result Regret bound of

ilde{\mathcal{O}}(\sqrt{H^5 M K} + εHK)

, independent of states and actions.

Reinforcement Learning Optimization Markov Decision Processes Aggregated States Regret Analysis

2019-12-13abs ↗pdf ↗

Reinforcement Learning with Action-Triggered Observationscs.LG

New framework for reinforcement learning with sporadic state observations.

problem Partial observability in reinforcement learning.

method Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs).

result Optimistic algorithm achieving regret bound for episodic learning.

Reinforcement Learning Partial Observability Sporadic Observations Markov Decision Processes Optimistic Algorithms

2025-10-02abs ↗pdf ↗

Off-Policy Evaluation for Episodic Partially Observable Markov Decision Processes under Non-Parametric Modelsstat.ML

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

problem Evaluating policies in partially observable environments without full model specification.

method Developed non-parametric identification and recursive fitted-Q-evaluation algorithm.

result Established finite-sample error bounds for policy value estimation.

Off-policy evaluation POMDPs Non-parametric models V-bridge functions Instrumental variables

2022-09-21abs ↗pdf ↗

Achieving

\varepsilon^{-2}

Dependence for Average-Reward Q-Learning with a New Contraction Principlecs.LG

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

problem Challenges in achieving optimal sample complexity for average-reward Q-learning.

method Synchronous and asynchronous Q-learning with a new contraction principle.

result Optimal

\widetilde{O}(\varepsilon^{-2})

sample complexity guarantees.

Q-learning Markov decision processes Contraction principle Average-reward Sample complexity

2026-01-29abs ↗pdf ↗

Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescs.LG

New RL algorithm achieves nearly optimal performance for linear MDPs.

problem Optimal reinforcement learning for episodic linear MDPs.

method Weighted linear regression with variance estimator and rare-switching policy.

result Achieves nearly minimax optimal regret

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

reinforcement learning linear MDPs regret minimization weighted regression variance estimator

2022-12-12abs ↗pdf ↗

A Doubly Robust Approach to Sparse Reinforcement Learningstat.ML

New algorithm minimizes regret in sparse reinforcement learning.

problem Sparse reinforcement learning with unknown sparsity.

method Doubly robust approach combining feature vectors of all actions and novel analysis.

result Regret bound of

ilde{O}(σ^{-1}_{\min} s_{\star} H \sqrt{N})

Reinforcement Learning Sparse Markov Decision Processes Doubly Robust Sparse Linear Regret Minimization

2023-10-23abs ↗pdf ↗

Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximationcs.LG

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

problem Risk-averse decision-making in Markov processes.

method Introduces mini-batch measures and multipattern risk-averse problems in a feature-based

Q

-learning method.

result Proves a high-probability regret bound of

\mathcal{O}\big(H^2 N^H \sqrt{ K}\big)

for the

Q

-learning method.

Reinforcement Learning Markov Decision Processes Risk Measures Mini-batch Measures Multipattern Risk

2026-05-01abs ↗pdf ↗

Online Markov Decision Processes with Terminal Law Constraintsmath.OC

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

problem Reset-free reinforcement learning with unknown dynamics and terminal law constraints.

method Periodic framework, periodic policies, periodic regret.

result First non-asymptotic guarantees for reset-free learning in multi-agent settings.

reinforcement learning Markov decision processes periodic policies terminal law constraints sublinear regret

2026-01-12abs ↗pdf ↗

Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteesstat.ML

OPSRL algorithm reduces regret with few samples in reinforcement learning.

problem High regret in reinforcement learning with limited data.

method Optimistic Posterior Sampling (OPSRL) with logarithmic sample complexity.

result Guaranteed high-probability regret bound of

\widetilde{\mathcal{O}}(\sqrt{H^3SAT})

reinforcement learning posterior sampling regret minimization Markov decision process few samples

2022-09-28abs ↗pdf ↗

Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcs.LG

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

problem Online learning in finite-horizon episodic MDPs with aggregate bandit feedback.

method Best-of-both-worlds (BOBW) algorithms using FTRL over occupancy measures, self-bounding techniques, and new loss estimators.

result First BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback achieving

O(\log T)

regret in stochastic and

{O}(\sqrt{T})

regret in adversarial settings.

online learning Markov decision processes aggregate bandit feedback regret minimization worst-case analysis

2025-10-20abs ↗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 ↗

Online learning in MDPs with linear function approximation and bandit feedbackcs.LG

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

problem Online learning in MDPs with changing reward functions and limited feedback.

method Developed MDP-LinExp3 algorithm with theoretical guarantees.

result Proved regret bounds for MDP-LinExp3 algorithm.

online learning Markov decision process linear function approximation bandit feedback regret analysis

2020-07-03abs ↗pdf ↗

UCB Momentum Q-learning: Correcting the bias without forgettingstat.ML

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

problem Improving Q-learning's bias and regret in reinforcement learning.

method UCBMQ combines Q-learning with an upper confidence bound and momentum term.

result UCBMQ guarantees a regret of

O(\sqrt{H^3SAT}+ H^4 S A )

with a linear second-order term in

S

reinforcement learning Q-learning momentum upper confidence bound regret

2021-03-01abs ↗pdf ↗

Counterfactual Off-Policy Evaluation with Gumbel-Max Structural Causal Modelscs.LG

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…

2019-05-14abs ↗pdf ↗

Toward the Fundamental Limits of Imitation Learningcs.LG

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.

imitation learning Markov Decision Processes minimax limits suboptimality bounds episodic MDPs

2020-09-13abs ↗pdf ↗

Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcs.LG

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…

2018-08-06abs ↗pdf ↗

Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscs.LG

Paper bounds PAC RL sample complexity in deterministic MDPs.

problem Identify ε-optimal policy with high probability.

method Proposes nearly matching upper and lower bounds on sample complexity, introduces deterministic return gap, uses graph-theoretical concepts and maximum-coverage exploration.

result First nearly matching upper and lower bounds on sample complexity for PAC RL in deterministic MDPs.

PAC reinforcement learning Markov decision processes sample complexity deterministic MDPs minimum flows

2022-03-17abs ↗pdf ↗

Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedbackcs.LG

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

problem Learning in episodic RMAB with unknown transition functions and adversarial rewards.

method Developed a novel RL algorithm with a biased reward estimator and an index policy.

result Achieved

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

regret bound for adversarial RMAB.

Reinforcement Learning RMAB Adversarial Unknown Transitions Bandit Feedback

2024-05-02abs ↗pdf ↗

Online learning in MDPs with side informationcs.LG

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…

2014-06-26abs ↗pdf ↗

Reinforcement Learning for Individual Optimal Policy from Heterogeneous Datastat.ML

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

problem Learning optimal policies for a heterogeneous population from pre-collected data.

method Individualized offline policy optimization framework for heterogeneous MDPs.

result The proposed P4L algorithm achieves a fast rate of average regret.

Reinforcement Learning Offline RL Heterogeneous Data Individual Policy Optimization Markov Decision Processes

2025-05-14abs ↗pdf ↗

Improved Algorithms for Misspecified Linear Markov Decision Processescs.LG

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

problem Misspecified linear Markov decision processes.

method Proposes an algorithm with three desirable properties: bounded regret, bounded space/time complexities, and no need for misspecification input.

result Regret scales as

K \max \{ \varepsilon_{ ext{mis}}, \varepsilon_{ ext{tol}} \}

, improving existing bounds.

misspecified MLMDP regret bounded complexity Sup-Lin-UCB contextual bandits

2021-09-12abs ↗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 ↗

Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcs.LG

New algorithm learns policies without explicit rewards for MDPs.

problem Learning policies for MDPs without explicit rewards.

method UCRL-RFE algorithm with linear function approximation.

result UCRL-RFE achieves optimal policy with minimal exploration samples.

reinforcement learning model-based reward-free UCRL-RFE linear function approximation

2021-10-12abs ↗pdf ↗

Efficient Learning in Non-Stationary Linear Markov Decision Processescs.LG

Optimistic algorithm reduces regret in non-stationary linear MDPs.

problem Efficient learning in non-stationary linear MDPs with evolving reward and transition.

method OPT-WLSVI, an optimistic model-free algorithm using exponential weights.

result Achieves a regret bound of

\widetilde{\mathcal{O}}(d^{5/4}H^2 Δ^{1/4} K^{3/4})

reinforcement learning non-stationary MDPs optimistic algorithms weighted least squares exponential weights

2020-10-24abs ↗pdf ↗

Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncs.LG

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

problem Model-free reinforcement learning in finite-horizon MDPs.

method Reference-Advantage decomposition for low regret.

result Achieves

ilde{O}(\sqrt{H^2SAT})

regret, matching best known bounds.

reinforcement learning finite-horizon MDPs UCB-Advantage regret bound model-free

2020-04-21abs ↗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 ↗

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 ↗

(More) Efficient Reinforcement Learning via Posterior Samplingstat.ML

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…

2013-06-04abs ↗pdf ↗

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescs.LG

New RL algorithm for linear MDPs with nearly optimal regret.

problem Optimizing reinforcement learning for linear mixture Markov decision processes.

method Proposed a new Bernstein-type concentration inequality for self-normalized martingales and a computationally efficient algorithm UCRL-VTR+.

result UCRL-VTR+ achieves nearly minimax optimal regret of