The paper introduces a new primal–dual algorithm for episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions. It achieves a rate‑optimal ×O(√K) regret and cumulative constraint violation, improving upon the previous ×O(K^{3/4}) bound and eliminating the need for Slater’s condition. The method combines adaptive FTRL, contracted value estimation, and an exponential Lyapunov function, enabling uniform concentration over the value function class and computational efficiency independent of the state‑space size.
By Kihyun Yu, Honghao Wei, Dabeen Lee
arXiv:2610. 13901v1 Announce Type: cross Abstract: We study the last iterate of standard asynchronous Q-learning from a single trajectory of a finite Markov decision process.
By Yang Peng
The paper introduces Anchored Neighborhood Optimization (ANO), a new policy‑optimization method that directly designs a smooth, bounded gain field for the probability‑ratio surrogate objective. ANO anchors the identity map at a ratio of one, peaks at a specified trust‑region boundary, and limits the influence of extreme off‑policy samples while providing a bounded, redescending pull on outliers. Empirical results show ANO consistently outperforms existing methods on Atari and MuJoCo benchmarks, and it remains robust under aggressive learning‑rate settings.
By Yiheng Zhang, Yiming Wang, Kaiyan Zhao, Zhenglin Wan, Jiayu Chen, Leong Hou U
arXiv:2609.13197v1 Announce Type: new
Abstract: Algorithmic Information Dynamics (AID) studies systems by perturbing them and measuring changes in algorithmic complexity, but its usual estimator, the...
By Luan Ozelim, Hector Zenil
arXiv:2302.07477v4 Announce Type: replace
Abstract: We study the optimal sample complexity of tabular reinforcement learning for infinite-horizon discounted Markov decision processes. The unrestricte...
By Shengbo Wang, Jose Blanchet, Peter Glynn
arXiv:2606. 11431v1 Announce Type: new Abstract: Mirror Descent (MD) extends Gradient Descent (GD) beyond Euclidean geometry and has recently reappeared as a lens for KL-regularized policy optimization in reinforcement learning and LLM post-training.
By Shira Vansover-Hager, Matan Schliserman, Ofir Schlisselberg, Tomer Koren
arXiv:2608. 08414v1 Announce Type: new Abstract: We study constrained statistical learning over infinite-dimensional hypothesis classes in the fully nonconvex setting, and establish universal PACC learnability of the solutions of dual algorithms: Probably Approximately Correct on Constraints, guaranteeing optimality and constraint satisfaction at once.
By Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias
arXiv:2606. 30789v1 Announce Type: new Abstract: Group Relative Policy Optimization (GRPO) has become a standard tool for improving the reasoning ability of large language models, yet its training dynamics are still described empirically: reward trajectories are fit with low-parameter functional forms whose constants carry no mechanistic meaning, and hyperparameter choices remain a matter of trial and error.
By Rajat Ghosh, Datta Nimmaturi, Aryan Singhal, Vaishnavi Bhargava, Henry Wong, Johnu George, Debojyoti Dutta
arXiv:2605. 01928v2 Announce Type: replace Abstract: We optimize losses that jump: spiking thresholds, quantized layers, and discrete routing put jumps in the forward pass, where backpropagation does not apply.
By An T. Le
arXiv:2607. 04470v1 Announce Type: cross Abstract: Large Language Models (LLMs) offer a natural interface for translating human objectives into reward signals for cooperative multi-agent reinforcement learning (MARL), yet the training-time dynamics of this integration remain poorly understood.
By Faid Keddouri, Sohaib Houhou, Aissa Boulmerka, Nadir Farhi
arXiv:2610.27321v1 Announce Type: cross
Abstract: Gradient descent with momentum can be viewed as a particle moving with friction in the loss landscape. In deep learning the learning rate is usually...
By Alexander Itin
The paper introduces REP-PD-TEG, a representation‑learning algorithm for low‑rank continuous‑state constrained Markov Decision Processes (CMDPs) that achieves optimal ≥O(√K) regret in the soft cumulative‑violation setting while maintaining a ≥O(K^{3/4}) sample bound when exploratory actions are penalised. For the stricter hard cumulative‑violation scenario, REP-PD-H-TEG is proposed, which uses a bonus‑corrected lower‑confidence utility certificate and a stabilized dual search to guarantee both regret and hard‑violation bounds. Together, these methods provide the first theoretically guaranteed representation‑learning framework for low‑rank continuous‑state CMDPs with both soft and hard violation controls.
By Chenhao Zhou, Chao Zhang, Wensong Bai, Hanbin Zhao, Hui Qian