UCB-Advantage learns MDPs with regret.
problem Model-free reinforcement learning in finite-horizon MDPs.
method Reference-Advantage decomposition for low regret.
result Achieves regret, matching best known bounds.
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.
169,181 papers · 148 categories
Trend · papers per month
48 results for “Finite-Horizon MDPs”
Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processescs.LG
The paper analyzes NPG in finite-horizon MDPs and provides convergence guarantees.
problem Finite-horizon Markov Decision Processes with known dynamics and transition kernels.
method Exact analysis of Natural Policy Gradient (NPG) with constant and increasing step sizes.
result NPG converges sublinearly with a rate of O(H^2/t) and linearly with a rate of O((1-1/θρ)^t).
Prior-Aligned Meta-RL: Thompson Sampling with Learned Priors and Guarantees in Finite-Horizon MDPscs.LG
New meta-reinforcement learning method improves performance in finite-horizon MDPs.
problem Improving meta-reinforcement learning in finite-horizon MDPs with shared optimal action-value functions.
method Proposes MTSRL and MTSRL+ algorithms with learned priors and covariance, coupled with prior-alignment technique for meta-regret guarantees.
result Achieves meta-regret guarantees with learned priors and covariance, outperforming prior-independent RL and bandit-only meta-baselines.
Kernel-UCBVI algorithm balances exploration and exploitation in metric state-action spaces.
problem Exploration-exploitation dilemma in finite-horizon reinforcement learning with metric state-action spaces.
method Kernel-UCBVI, leveraging smoothness and kernel estimators of rewards and transitions.
result First regret bound for kernel-based RL using smoothing kernels, .
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.
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 regret for K ≥ 2.
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 …
Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Samplingcs.LG
New IS methods fail to reduce variance in long-horizon MDPs.
problem High variance in off-policy evaluation for long-horizon domains.
method Conditional Monte Carlo analysis of IS methods.
result No strict variance reduction for per-decision or stationary IS methods in finite horizon MDPs.
New RL difficulty shown for discounted settings.
problem Difficulty in reinforcement learning with discounted rewards.
method Adapted Wang et al. (2020) construction to 2-state MDP.
result Learning impossible even with infinite data in discounted setting.
New algorithms ensure policies perform at least as good as a baseline in reinforcement learning.
problem Learning policies that are guaranteed to perform at least as well as a baseline in reinforcement learning.
method Introduce conservative exploration for average reward and finite horizon problems, presenting two optimistic algorithms.
result Guaranteed performance of policies at least as good as a baseline, without hindering learning ability.
NVMDP framework tackles non-stationary MDPs with varying discount rates.
problem Challenges in non-stationary environments and infinite-horizon formulations for reinforcement learning.
method Introduces NVMDP framework that accommodates non-stationarity and varying discount rates.
result NVMDPs provide a flexible mechanism to shape optimal policies without altering state or action spaces.
Paper identifies reductive MDPs, solving them in polynomial time.
problem Computational hardness of general MDPs and tractability of finite-horizon MDPs.
method Defines reductivity, a new class of SSPs, and develops a polynomial-time solution.
result Optimal policies can be found in polynomial time for reductive SSPs and MDPs.
Q-MMR evaluates policies using reweighted rewards and moment matching.
problem Off-policy evaluation in finite-horizon MDPs.
method Q-MMR learns scalar weights for data points via a moment matching objective against a value-function discriminator class.
result Data-dependent finite-sample guarantee with a dimension-free error bound.
New algorithm reduces offline RL data requirements significantly.
problem Optimizing policies using only historical data in reinforcement learning.
method Off-Policy Double Variance Reduction (OPDVR) algorithm.
result OPDVR achieves optimal sample complexity with episodes.
New algorithms learn MDPs with better regret bounds using generative sampling.
problem Learning MDPs with optimal policies under uncertainty.
method Hybrid exploration-generative RL model, classical and quantum algorithms.
result Quantum algorithms achieve regret for infinite-horizon MDPs.
Improved Q-learning with UCB for infinite-horizon MDPs with sample complexity bound.
problem Sample efficiency of Q-learning with UCB for infinite-horizon MDPs.
method Adapted Q-learning with UCB-exploration bonus for infinite-horizon MDPs without generative model.
result Sample complexity of exploration is bounded by O({ rac{SA}{ε^2(1-γ)^7}}), improving previous results.
We study the online estimation of the optimal policy of a Markov decision process (MDP). We propose a class of Stochastic Primal-Dual (SPD) methods which exploit the inherent minimax duality of Bellman equations. The SPD methods update a few coordinates of the value and policy estimates as a new state transition is obs…
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.
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.
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 per episode.
Optimal policy for multi-armed multi-action bandits with unknown parameters.
problem Optimal sequential action selection for multi-armed multi-action bandits with unknown parameters.
method Occupancy-Measured-Reward Index Policy (OMRIP) and R(MA)^2B-UCB algorithm.
result Asymptotically optimal policy with sub-linear regret and low computational complexity.
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.
Efficient algorithm for learning MDPs with unknown transitions and bandit feedback.
problem Learning in episodic finite-horizon MDPs with unknown transitions and bandit feedback.
method Proposes an efficient algorithm with regret.
result Achieves regret, matching previous work with full-information feedback.
Optimistic actor-critic tackles linear MDPs with parametric policies.
problem Theoretical limitations of existing actor-critic methods for linear MDPs.
method Proposes an optimistic actor-critic framework with parametric log-linear policies and approximate Thompson sampling.
result Achieves state-of-the-art sample complexity in both on-policy and off-policy settings.
New method improves RL in continuous spaces with kernel smoothing.
problem Sample efficiency and structural assumptions in classical RL.
method Kernel smoothing model-based approach with Bernstein-style exploration bonus.
result Achieves improved regret bound in finite-horizon settings.
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.
New bounds assess policy evaluation under unobserved confounders, showing model-based methods are more effective.
problem Policy evaluation under unobserved confounders in uncertain causal environments.
method Developed worst-case bounds for sensitivity to unobserved confounders, demonstrating model-based methods are more effective.
result Model-based approaches with robust MDPs provide sharper lower bounds for policy evaluation.
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 -type regret and communication cost bounds.
New algorithm learns optimal policies with just 1 episode, settling horizon-dependence in RL.
problem Understanding the sample complexity of reinforcement learning with horizon length.
method Developed an algorithm using only episodes to achieve PAC guarantee, leveraging connections between value functions in discounted and finite-horizon MDPs and novel perturbation analysis.
result Achieved the same PAC guarantee with only episodes of environment interactions, completely settling horizon-dependence in RL.
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.
The paper studies reward concentration in MDPs, covering asymptotic and non-asymptotic settings.
problem Reward concentration in Markov Decision Processes (MDPs).
method Unified approach to reward concentration in MDPs, including asymptotic and non-asymptotic bounds.
result Rate-equivalent definitions of regret for learning policies.
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 regret in stochastic and regret in adversarial settings.
Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-world applications, an interactive learning agent operates for a fixed or bounded period of time, for ex…
Adversarial online multi-task RL with task separation.
problem Minimize regret in an adversarial online multi-task setting with unknown MDPs.
method Prove minimax and instance-specific lower bounds, develop a clustering algorithm with optimal sample complexity and regret.
result Tight sample complexity and regret bounds for adversarial online multi-task RL.
AIF reformulated as convex MDP for adaptive behavior.
problem Adaptive behavior and policy optimization.
method Formulating AIF as convex MDP, deriving mirror descent algorithm.
result EFE minimization in AIF is equivalent to reward maximization in latent MDP, with epistemic component.
Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Randomstat.ML
Off-policy evaluation for MNAR rewards in MDPs
problem Off-policy evaluation in MDPs with MNAR rewards
method Formalizing a reward-dependent propensity model and using future states as shadow variables
result Proposed an Fitted-Q-Evaluation-style estimator that propagates recovered rewards while allowing target policies to depend on past missingness indicators
New RL algorithm gives tighter bounds without domain knowledge.
problem Improving worst-case performance bounds in reinforcement learning.
method Derives algorithm for finite horizon discrete MDPs with analysis yielding state-of-the-art worst-case regret bounds.
result Substantially tighter bounds for environments with small environmental norm, no prior knowledge required.
This paper improves Q-learning bounds using reference-advantage decomposition.
problem Improving Q-learning bounds in MDPs with positive suboptimality gaps.
method Develops a novel error decomposition framework to prove gap-dependent regret bounds.
result Establishes logarithmic gap-dependent regret bounds for Q-learning.
This work improves Q-learning for average-reward MDPs, reducing sample and communication complexities in federated settings.
problem Improving sample complexity of Q-learning for average-reward MDPs.
method Simple Q-learning algorithm with carefully chosen parameters for both single-agent and federated scenarios.
result Established first federated Q-learning algorithm for average-reward MDPs with provable efficiency in sample and communication complexities.
Paper establishes lower bounds and optimal algorithms for deployment-efficient RL.
problem Deployment efficiency in reinforcement learning.
method Optimization with constraints, lower bounds, algorithms.
result Established optimal algorithms for deployment-efficient RL.
This paper shows CEM is a special case of TTM, leading to new proofs and improved sample complexity bounds.
problem Improving sample complexity for reinforcement learning algorithms.
method Viewing CEM as an application of TTM, deriving new proofs and bounds.
result Improved sample complexity bounds for CEM under various conditions.
Reward tweaking optimizes behavior for long-term goals by adjusting the reward function.
problem Optimizing behavior for long-term goals in reinforcement learning with unstable long planning horizons.
method Reward tweaking learns a surrogate reward function that induces optimal behavior for the original task.
result Reward tweaking guides agents towards better long-term returns while planning for short horizons.
Quantum UCB algorithm reduces reinforcement learning regret exponentially.
problem Episodic reinforcement learning with quantum state evolution.
method Upper Confidence Bound (UCB) quantum algorithm with quantum mean estimation.
result Exponential improvement in regret from $\Tilde{\mathcal{O}}(\sqrt{K})$ to $\Tilde{\mathcal{O}}(1)$.
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.
Greedy policies in model-based RL achieve tight regret bounds without full planning.
problem Achieving efficient RL algorithms in MDP settings.
method Using greedy policies for 1-step planning in model-based RL.
result Greedy policies achieve regret bounds.
Paper overcomes sample size barrier in reinforcement learning with generative models.
problem Sample efficiency in reinforcement learning with generative models.
method Developed two algorithms to certify minimax optimality of sample complexity.
result Achieved minimax-optimal guarantees for a wide range of sample sizes.
This is a brief technical note to clarify some of the issues with applying the application of the algorithm posterior sampling for reinforcement learning (PSRL) in environments without fixed episodes. In particular, this paper aims to: - Review some of results which have been proven for finite horizon MDPs (Osband et a…
Regularized greedy policies outperform classical greedy in finite-horizon bandit problems.
problem Optimizing decision-making in sequential experiments with finite time constraints.
method Developed regularized greedy algorithms for multi-armed Bernoulli bandits.
result Calibrated regularized greedy policies consistently match or outperform state-of-the-art algorithms.