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 “tabular MDPs”

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 ↗

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 ↗

Towards Instance-Optimality in Online PAC Reinforcement Learningstat.ML

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

problem Identifying near-optimal policies in tabular MDPs with minimal samples.

method Proposes instance-dependent lower bound for sample complexity.

result Lower bound closely matches PEDEL algorithm's sample complexity.

PAC reinforcement learning instance-dependent lower bound sample complexity near-optimal policies tabular MDPs

2023-10-31abs ↗pdf ↗

Model-free Posterior Sampling via Learning Rate Randomizationstat.ML

RandQL is a new model-free algorithm for MDPs with a novel learning rate randomization approach.

problem Minimizing regret in episodic MDPs with model-free methods.

method Randomized Q-learning with learning rate randomization.

result RandQL achieves optimal regret bounds in both tabular and metric state-action spaces.

Randomized Q-learning Model-free Regret minimization Episodic MDPs Learning rate randomization

2023-10-27abs ↗pdf ↗

Nearly Horizon-Free Offline Reinforcement Learningstat.ML

New method achieves nearly horizon-free offline reinforcement learning for tabular and linear MDPs.

problem Achieving efficient reinforcement learning without knowing the horizon.

method Simple recursion-based method to bound total variance in offline scenarios.

result Nearly horizon-free sample complexity bounds for offline policy evaluation and optimization.

reinforcement learning offline learning Markov Decision Processes horizon-free sample complexity

2021-03-25abs ↗pdf ↗

Reinforcement Learning from Adversarial Preferences in Tabular MDPscs.LG

New framework for reinforcement learning with adversarial preferences in tabular MDPs.

problem Learning from preferences rather than direct rewards in MDPs with adversarial settings.

method Developed PbMDPs framework, established lower bounds, and proposed algorithms for regret minimization.

result Achieved regret bounds of

Ω( (H^2 S K)^{1/3} T^{2/3} )

for PbMDPs with Borda scores.

Reinforcement Learning MDPs Adversarial Preferences Borda Scores Regret Minimization

2025-07-15abs ↗pdf ↗

Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscs.LG

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\wid…

2019-05-09abs ↗pdf ↗

A Model Selection Approach for Corruption Robust Reinforcement Learningcs.LG

New model selects robustly in adversarial reinforcement learning with unknown corruption.

problem Adversarial corruption in reinforcement learning with unknown total corruption amount.

method Model selection approach for finite-horizon tabular and linear MDPs.

result First worst-case optimal bound without knowledge of total corruption.

reinforcement learning corruption robustness model selection adversarial tabular MDPs

2021-10-07abs ↗pdf ↗

Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPsstat.ML

Hybrid RL algorithms improve offline and online RL in linear MDPs.

problem Improving RL performance without single-policy concentrability.

method Developed computationally efficient algorithms for PAC and regret-minimizing RL in linear MDPs.

result Achieved sharper error or regret bounds for linear MDPs.

Hybrid RL PAC RL Regret-minimizing RL Linear MDPs Offline RL

2024-08-08abs ↗pdf ↗

Optimal Sample Complexity of Reinforcement Learning for Mixing Discounted Markov Decision Processescs.LG

New RL theory reduces sample complexity for mixing MDPs.

problem Optimal sample complexity for reinforcement learning in mixing MDPs.

method Regeneration-type ideas to analyze mixing times.

result Optimal sample complexity depends on mixing time, not just discount factor.

reinforcement learning Markov decision process mixing sample complexity regeneration

2023-02-15abs ↗pdf ↗

Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcs.LG

Optimal strategy for reinforcement learning with delayed observations.

problem Delayed state observation in reinforcement learning.

method Combines augmentation method and upper confidence bound approach.

result Minimax optimal regret bound of

ilde{\mathcal{O}}(H \sqrt{D_{\max} SAK})

reinforcement learning delayed observations upper confidence bound minimax optimal tabular MDPs

2026-03-03abs ↗pdf ↗

Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPscs.LG

In order to make good decision under uncertainty an agent must learn from observations. To do so, two of the most common frameworks are Contextual Bandits and Markov Decision Processes (MDPs). In this paper, we study whether there exist algorithms for the more general framework (MDP) which automatically provide the bes…

2019-11-03abs ↗pdf ↗

Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholdingcs.LG

New RL method learns K-step lookahead Q-functions for fixed-horizon MDPs.

problem Challenges in online reinforcement learning for non-episodic, finite-horizon MDPs.

method Introduces a K-step lookahead Q-function with a time-varying threshold for selecting actions.

result Achieves minimax optimal constant regret for K=1 and

\mathcal{O}(\max((K-1),C_{K-1})\sqrt{SAT\log(T)})

regret for K ≥ 2.

reinforcement learning finite horizon lookahead Q-function thresholding tabular learning

2026-01-31abs ↗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 ↗

Data- and Variance-dependent Regret Bounds for Online Tabular MDPscs.LG

New algorithms reduce regret in online MDPs by adapting to data and variance.

problem Adapting to both adversarial and stochastic environments in online MDPs.

method Develops algorithms based on global optimization and policy optimization, using optimistic follow-the-regularized-leader with log-barrier regularization.

result Achieves refined data-dependent and variance-dependent regret bounds.

online MDPs regret bounds adversarial regime stochastic regime optimistic follow-the-regularized-leader

2026-02-02abs ↗pdf ↗

Optimistic Planning by Regularized Dynamic Programmingcs.LG

New method for optimistic planning in MDPs using regularization.

problem Optimistic planning in infinite-horizon discounted MDPs.

method Regularized dynamic programming for approximate value iteration.

result Achieves near-optimal statistical guarantees in learning policies.

optimistic planning dynamic programming regularization Markov decision processes approximate value iteration

2023-02-27abs ↗pdf ↗

Active Reinforcement Learning with Monte-Carlo Tree Searchcs.LG

Active Reinforcement Learning (ARL) is a twist on RL where the agent observes reward information only if it pays a cost. This subtle change makes exploration substantially more challenging. Powerful principles in RL like optimism, Thompson sampling, and random exploration do not help with ARL. We relate ARL in tabular …

2018-03-13abs ↗pdf ↗

A Reduction-Based Framework for Conservative Bandits and Reinforcement Learningcs.LG

Paper presents a reduction-based framework for conservative bandits and RL with improved lower and upper bounds.

problem Conservative bandits and reinforcement learning problems.

method Reduction technique to calculate necessary and sufficient budget from baseline policy.

result Improved lower and upper bounds for various conservative settings.

Conservative bandits Reinforcement learning Reduction technique Lower bounds Upper bounds

2021-06-22abs ↗pdf ↗

Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcs.LG

Safe exploration in RF-RL doesn't increase sample complexity.

problem Achieving optimal policies with safety constraints in reward-free RL.

method Proposed SWEET framework for tabular and low-rank MDP settings, leveraging truncated value functions.

result Sample complexities match or outperform constraint-free counterparts, proving safety constraints have little impact.

reward-free reinforcement learning safe exploration sample complexity truncated value functions tabular MDP

2022-06-28abs ↗pdf ↗

Scalable methods for computing state similarity in deterministic Markov Decision Processescs.LG

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…

2019-11-21abs ↗pdf ↗

Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscs.LG

Efficient RL for linear MDPs with unknown transitions.

problem Long planning horizons and unknown state transitions in linear mixture MDPs.

method Horizon-free algorithm using weighted least squares with variance and uncertainty awareness.

result Achieves optimal regret up to logarithmic factors.

Reinforcement Learning Horizon-Free Linear Mixture MDPs Weighted Least Squares Regret Minimization

2022-05-23abs ↗pdf ↗

Non-stationary Reinforcement Learning under General Function Approximationcs.LG

New algorithm tackles non-stationary reinforcement learning with general function approximation.

problem Understanding non-stationary MDPs with function approximation.

method Dynamic Bellman Eluder (DBE) dimension for complexity, sliding window mechanism, confidence set design.

result Upper bound on dynamic regret for proposed SW-OPEA algorithm.

non-stationary reinforcement learning dynamic Bellman Eluder dimension confidence set sliding window dynamic regret

2023-06-01abs ↗pdf ↗

Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecs.LG

New algorithm for offline RL with linear approx in MDPs and MGs, nearly optimal.

problem Offline RL with linear function approximation in MDPs and MGs.

method Pessimism-based algorithm with uncertainty decomposition via reference function.

result Nearly minimax optimal performance in offline RL for MDPs and MGs.

Offline RL Linear function approximation MDP MG Pessimism

2022-05-31abs ↗pdf ↗

Information-Theoretic Confidence Bounds for Reinforcement Learningstat.ML

We integrate information-theoretic concepts into the design and analysis of optimistic algorithms and Thompson sampling. By making a connection between information-theoretic quantities and confidence bounds, we obtain results that relate the per-period performance of the agent with its information gain about the enviro…

2019-11-21abs ↗pdf ↗

On the Linear Convergence of Policy Gradient under Hadamard Parameterizationmath.OC

Policy gradient converges linearly with Hadamard parameterization in tabular settings.

problem Convergence of policy gradient methods under Hadamard parameterization.

method Studied convergence rate and established linear convergence after

k_0

iterations.

result Algorithm converges linearly with rate $O(rac{1}{k})$ and faster locally after

k_0

policy gradient Hadamard parameterization linear convergence tabular settings local linear convergence

2023-05-31abs ↗pdf ↗

Provably Efficient CVaR RL in Low-rank MDPscs.LG

New RL algorithm maximizes CVaR in low-rank MDPs with provable efficiency.

problem Maximizing CVaR in large state spaces with function approximation.

method Upper Confidence Bound (UCB) bonus-driven algorithm for low-rank MDPs.

result Achieves sample complexity of O(H^7 A^2 d^4 / τ^2 ε^2) for ε-optimal CVaR.

Reinforcement Learning Conditional Value at Risk Low-rank MDPs Upper Confidence Bound Function Approximation

2023-11-20abs ↗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 ↗

Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescs.LG

Improved exploration in adversarial MDPs via dilated bonuses.

problem Global exploration in adversarial MDPs with local-search policies.

method Dilated bonuses to facilitate global exploration.

result Improved regret bounds in various MDP settings.

Policy Optimization Reinforcement Learning Adversarial MDPs Global Exploration Dilated Bonuses

2021-07-18abs ↗pdf ↗

Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationstat.ML

Entropy-regularized NPG methods converge linearly in discounted MDPs.

problem Theoretical limitations of NPG methods in reinforcement learning.

method Entropy regularization in conjunction with NPG methods for discounted MDPs.

result Entropy-regularized NPG methods converge linearly in discounted MDPs.

reinforcement learning natural policy gradient entropy regularization discounted MDPs convergence guarantees

2020-07-13abs ↗pdf ↗

Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodsmath.OC

Paper analyzes convergence of dynamic policy gradient for MDPs, improving performance in finite-time problems.

problem Optimal policies in finite-time MDPs are not stationary and require epoch-specific training.

method Introduces dynamic policy gradient combining dynamic programming and policy gradient, analyzes convergence for softmax parametrisation.

result Dynamic policy gradient training exploits finite-time structure, leading to better convergence bounds.

policy gradient dynamic programming finite horizon MDPs softmax parametrisation convergence analysis

2023-10-04abs ↗pdf ↗

Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approachstat.ML

The paper introduces a method to learn and apply value envelopes for faster online reinforcement learning.

problem Accelerating online reinforcement learning using offline data with theoretical grounding.

method A two-stage framework: offline data for learning value bounds, online algorithms for applying them.

result Substantial regret reductions in empirical tests on tabular MDPs.

reinforcement learning online algorithms value envelopes offline data tabular MDPs

2025-10-22abs ↗pdf ↗

Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescs.LG

Reward-free RL in linear MDPs is as hard as reward-aware RL.

problem Reward-free RL in linear MDPs without access to the reward function during exploration.

method Developed a computationally efficient algorithm with sample complexity

\widetilde{\mathcal{O}}(d^2 H^5/ε^2)

result Achieved optimal

d

dependence in linear MDPs for reward-free RL, matching the reward-aware RL setting.

reinforcement learning reward-free linear MDPs sample complexity feature direction

2022-01-26abs ↗pdf ↗

Convergence of Policy Gradient for Entropy Regularized MDPs with Neural Network Approximation in the Mean-Field Regimemath.OC

Study shows policy gradient convergence for entropy-regularized MDPs with neural nets in mean-field regime.

problem Global convergence of policy gradient for entropy-regularized MDPs with neural network approximation.

method Softmax policy with neural network approximation in mean-field regime, gradient flow in 2-Wasserstein metric, exponential convergence under sufficient regularization.

result Gradient flow converges exponentially fast to the unique stationary solution under sufficient regularization.

policy gradient entropy regularization Markov decision processes mean-field regime neural networks

2022-01-18abs ↗pdf ↗

Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcs.LG

This paper improves reinforcement learning efficiency for large-scale MDPs.

problem High sample complexity in tabular RL settings with large state and action spaces.

method Model-based approach and Q-learning with linearly parameterized features.

result Provably efficient learning with sample complexity bounds.

reinforcement learning MDP generative model sample efficiency linearly parameterized

2021-05-28abs ↗pdf ↗

Exact Unlearning in Reinforcement Learningcs.LG

A new RL framework allows removing user data without affecting performance.

problem Efficiently removing user data from a reinforcement learning model without affecting performance.

method Formulated a

ρ

-TV-stable RL algorithm for tabular MDPs that supports exact unlearning.

result Achieved a nearly minimax optimal regret bound of

Ω(H\sqrt{\!SAT}\! +\! {SAH}/ρ)

for

ρ

-TV-stable RL algorithms.

reinforcement learning unlearning tabular MDPs TV-stability regret bound

2026-06-02abs ↗pdf ↗

Settling the Sample Complexity of Model-Based Offline Reinforcement Learningstat.ML

This paper is concerned with offline reinforcement learning (RL), which learns using pre-collected data without further exploration. Effective offline RL would be able to accommodate distribution shift and limited data coverage. However, prior algorithms or analyses either suffer from suboptimal sample complexities or …

2022-04-11abs ↗pdf ↗

Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscs.LG

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

problem Assigning credit to actions in reinforcement learning with only endpoint rewards.

method Develops a provably sample-efficient algorithm for online reinforcement learning with general function approximation.

result Achieves

O(C_{ m cov} H^3/ε^2)

sample complexity, characterizing statistical separation between outcome-based and per-step rewards.

reinforcement learning outcome-based feedback sample complexity function approximation statistical efficiency

2025-05-26abs ↗pdf ↗

Efficient Model-free Reinforcement Learning in Metric Spacescs.LG

Model-free Reinforcement Learning (RL) algorithms such as Q-learning [Watkins, Dayan 92] have been widely used in practice and can achieve human level performance in applications such as video games [Mnih et al. 15]. Recently, equipped with the idea of optimism in the face of uncertainty, Q-learning algorithms [Jin, Al…

2019-05-01abs ↗pdf ↗

Transformers Provably Implement In-Context Reinforcement Learning with Policy Improvementstat.ML

Transformers can implement reinforcement learning algorithms from data without updates.

problem Training reinforcement learning algorithms from data without parameter updates.

method Design a teacher-mimicking training procedure for transformers to implement policy-improvement methods.

result Gradient flow converges to an optimal parameter manifold corresponding to the desired RL update.

transformers in-context reinforcement learning policy improvement gradient flow reinforcement learning algorithms

2026-05-07abs ↗pdf ↗

Gap-Dependent Bounds for Federated

Q

-learningstat.ML

New method reduces regret and communication costs in federated Q-learning.

problem Worst-case regret and communication cost bounds in federated Q-learning.

method Gap-dependent analysis leveraging MDP structures.

result Achieves

\log T

-type regret and communication cost bounds.

Federated Q-learning Regret bounds Communication cost MDPs Gap-dependent analysis

2025-02-05abs ↗pdf ↗

Regret Bounds for Information-Directed Reinforcement Learningcs.LG

New bounds on IDS for RL show how to balance computation and learning efficiency.

problem Understanding and optimizing information-directed sampling (IDS) for reinforcement learning.

method Developed novel information-theoretic tools to bound information ratio and cumulative information gain.

result Derived prior-free Bayesian regret bounds for IDS in tabular finite-horizon MDPs and improved computational efficiency.

reinforcement learning information-directed sampling regret bounds Markov Decision Processes Bayesian

2022-06-09abs ↗pdf ↗

Model-Based Uncertainty in Value Functionscs.LG

New method quantifies uncertainty in reinforcement learning models.

problem Quantifying uncertainty over expected cumulative rewards in reinforcement learning.

method Proposes a new uncertainty Bellman equation to more accurately estimate value function variance.

result Our method converges to the true posterior variance over values and improves sample-efficiency.

reinforcement learning uncertainty quantification value function Bellman equation exploration

2023-02-24abs ↗pdf ↗

Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learningstat.ML

Study non-asymptotic BPI guarantees for online RL.

problem Identify optimal policy in MDP with high confidence.

method Non-asymptotic sample complexity guarantees for NaS algorithm.

result Sample complexity depends on MDP connectivity and curvature.

Reinforcement Learning Best Policy Identification Online Learning Markov Decision Process Non-asymptotic Analysis

2026-07-19abs ↗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 Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcs.LG

Paper presents an efficient algorithm for linear MDP with low switching cost.

problem Large state space reinforcement learning problems with low switching cost.

method First algorithm for linear MDP with low switching cost, achieving near-optimal regret and switching cost.

result Regret bound of $\widetilde{O}\left(\sqrt{d^3H^4K} ight)$ and near-optimal switching cost of $O\left(d H\log K ight)$.

reinforcement learning Markov decision process linear function approximation regret bound switching cost

2021-01-02abs ↗pdf ↗

GAN Q-learningstat.ML

Distributional reinforcement learning (distributional RL) has seen empirical success in complex Markov Decision Processes (MDPs) in the setting of nonlinear function approximation. However, there are many different ways in which one can leverage the distributional approach to reinforcement learning. In this paper, we p…

2018-05-13abs ↗pdf ↗

A Note on Target Q-learning For Solving Finite MDPs with A Generative Oraclecs.LG

Improved sample complexity for target Q-learning in finite MDPs with generative oracle.

problem Sample complexity of target Q-learning in finite MDPs with a generative oracle.

method Analyzed target Q-learning algorithm in tabular case with a generative oracle, improved sample complexity.

result Improved sample complexity for target Q-learning in various scenarios.

Q-learning target network sample complexity finite MDPs generative oracle

2022-03-22abs ↗pdf ↗

Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecs.LG

New algorithm learns optimal policies with minimal memory and time.

problem Learning optimal policies in discounted MDPs with short burn-in time.

method Variance reduction and adaptive policy switching.

result First regret-optimal model-free algorithm with low burn-in time.

reinforcement learning discounted MDPs regret minimization policy switching variance reduction

2023-05-24abs ↗pdf ↗