跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1959新增论文
+1550其中 AI 相关
+212已有论文修订
+73新增 AI 导读

arXiv 最近完成扫描:2026-11-17 23:20 · 全站最近入库:2026-11-17 23:35各信源进度 →

统计口径与数据新鲜度

统计 2026-11-17 00:54 — 2026-11-18 00:54(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-17 23:20最近发现新增版本:2026-11-17 23:35库内论文最新更新时间:2026-11-17 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

25,786 已收录论文21,491 AI 相关7,725 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 4 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 23:19(北京时间)
新论文 · v1arXiv:2611.19566

Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL

Matthew Zurek, Yudong Chen

原文摘要

We study the sample complexity of the empirical planning or plug-in approach for reinforcement learning (RL) with a generative model. We show the discounted plug-in approach finds an $\varepsilon$-optimal policy with $O(SA (1-γ)^{-3} \varepsilon^{-2} \log(SA/δ))$ samples, where $S, A, γ, δ$ are the state and action sizes, discount factor, and failure probability, respectively. In the average-reward setting, we show that discounted plug-in and direct (undiscounted) plug-in achieve $O(SAH\varepsilon^{-2}\log(SA/δ))$ and $O(SAD\varepsilon^{-2}\log(SA/δ))$ complexities, respectively, where $H$ upper-bounds the optimal bias span and $D$ is the diameter. Combining with our lower bounds for nonadaptive generative models, these results resolve the minimax sample complexity of discounted RL and average-reward RL --- in both the span- and diameter-based classes --- up to constant factors. Our main technical contribution is a novel Bellman residual bracketing technique which improves the efficiency of prior absorbing-MDP-based concentration analyses.

cs.LG · cs.IT · math.OC · math.PR · stat.ML

版本更新 · v3arXiv:2606.14095

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

Tianhao Wu, Matthew Zurek, Weina Wang, Qiaomin Xie

原文摘要

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms $N$. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in $N$. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an $O(1/\sqrt{N})$ optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.

cs.LG · math.OC · math.PR · stat.ML

新论文 · v1arXiv:2610.40165

Closing the Log Gap: Minimax-Optimal Regret for Episodic RL

Guy Zamir, Victor Boone, Matthew Zurek, Yudong Chen

原文摘要

In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as $\sqrt{H^3 S A K}$ for sufficiently large $K$, where $H$ is the episode length, $K$ is the number of episodes, and $S$ and $A$ are the numbers of states and actions, respectively. Our method is the first to match the minimax lower bound \emph{without extra polylog factors}. We introduce a variant of UCBVI which does not maintain strictly optimistic estimates, and uses MOSS-style exploration bonuses whose logarithmic terms adapt to both visit counts and estimated variances. A key challenge is controlling the propagation of errors caused by under-optimism, which we accomplish in an occupancy-weighted way, avoiding logarithmic overhead that would be incurred by uniform-over-rows concentration. Our analysis develops time-uniform and variance-aware concentration bounds that may be of independent interest. As a corollary we also develop an algorithm for $(\varepsilon, δ)$-PAC best-policy identification, which is the first to match the $Ω\big(H^3 SA\log(\frac{1}δ)\varepsilon^{-2}\big)$ minimax lower bound up to constants in some regimes.

cs.LG · stat.ML

新论文 · v1arXiv:2610.38313

Game-Theoretic Foundations for Undiscounted Bisimulation Metrics

Matthew Zurek, Yudong Chen, Josiah P. Hanna

原文摘要

Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when $γ=1$. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally, we prove that these metrics bound total-reward and, when the optimal gain is state-independent, optimal relative value differences. We also provide error and suboptimality guarantees for aggregation-based planning in total- and average-reward settings.

cs.AI · cs.GT · cs.LG · math.OC