Optimal

Follow this topic Ask about this topic

Momentum

8 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 36

All topics

Rate-Optimal Algorithm for Adversarial Linear CMDPs
Oct 1, 2026Kihyun Yu, Honghao Wei, Dabeen LeeMarkov Decision Processes Primal-Dual Methods
KAIST · Washington State University · Seoul National University
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
Sep 29, 2026Kaixuan Ji, Qiwei Di, Qingyue Zhao +2Stochastic Multi-Armed Bandits Bandits
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
Hyperbolic Multimodal Continual Learning: A Closest-Admissible Solution
Sep 24, 2026Jiahong Liu, Ming Shen, Xiaohao Liu +4Multimodal Learning Replay-Based Continual Learning
The Chinese University of Hong Kong · National University of Singapore · Yale University +1
Do AI Agents Understand Computer Architecture?
Sep 16, 2026Ambika Sharan, Grigory Chirkov, Soheil AbbaslooHardware Efficiency Artificial Intelligence Agents
Microsoft Research
Regularized Least Squares Training of Quadratic Neural Networks with Applications to System Identification
Sep 15, 2026Luis Rodrigues, Zachary Yetman Van Egmond, Mohammad R. Amiri FardLeast Squares System Identification
Department of Electrical and Computer Engineering Concordia University Montr´eal, QC, Canada
Optimal Value Inference for Reinforcement Learning
Sep 9, 2026Nan Lu, Ethan Lee, James M. Robins +2Value Functions Bellman Equation
Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
Sep 8, 2026Ivan Lau, Jonathan ScarlettOptimal Sample Complexity Minimax Rate
National University of Singapore
La Agente 'Optima: Towards Agentic Self-Driving Laboratories
Sep 7, 2026Marcel Müller, Jiaru Bai, Willi Gottstein +14Agentic Optimization Laboratory
Department of Chemistry, University of Toronto, 80 St. George St., Toronto, ON M5S 3H6, Canada · Vector Institute for Artificial Intelligence, W1140-108 College St., Schwartz Reisman Innovation Campus, Toronto, ON2026 M5G 0C6, Canada · Acceleration Consortium, 700 University Ave., Toronto, ON M7A 2S4, Canada +11
Advances in Machine Learning for Directed Evolution: A Five-Year Retrospective
Sep 2, 2026Bruce J. WittmannProtein Design Evolutionary Optimization Methods
Microsoft, Office of the Chief Scientific Officer
Keep, Customize, or Exit: Default Design and Token Pricing in LLM Reasoning Services
Aug 13, 2026Ahmet Bugra Gundogan, Yigit Turkmen, Melih BastopcuEquilibrium Optimal
Department of Electrical and Electronics Engineering
Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening
Aug 5, 2026Mark Bedaywi, Scott Emmons, Nika Haghtalab +1Multi-Agent Coordination Protocol
University of California, Berkeley
AtumAI: A Principled Framework for Agentic Generation of Datacenter Control-Plane Policies
Aug 3, 2026Qiushi Lin, Chaojie Zhang, Íñigo Goiri +3Artificial Intelligence Infrastructure Data Centers
The University of Texas at Austin · Microsoft Azure
Learning to Persuade Privately Informed Receivers
Jul 30, 2026I. Arda Vurankaya, Ufuk TopcuPersuasion Private Signals
The University of Texas at Austin
Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search
Jul 26, 2026Haijiang Yan, Jian-Qiao Zhu, Liqiang Huang +1Salesman Problem Combinatorial Optimization
Department of Psychology, The University of Warwick, Coventry, United Kingdom. · Department of Psychology, The University of Hong Kong, Hong Kong, China. · Department of Psychology, The Chinese University of Hong Kong, Hong Kong, China. +2
Try Once, Then Optimal: De-Redundified Procedure Memory for Cross-Episode Exploration Amortization
Jul 26, 2026Haizhou Ge, Haochen Ouyang, Zhixing Chen +6Episodic Memory Exploration
1Tsinghua University. · 3Northeast Agricultural University. · 2DISCOVER Robotics.
DASH Robot: Minimalistic Design and Optimal Aerial-Terrestrial Locomotion via Contact-Implicit Control
Jul 20, 2026Ryan Gomes Paiva, Conrad Ho, Jiarong Kang +3Aerial Robots Locomotion
University of Wisconsin–Madison, WI, USA. · Shanghai Innovation Institute (SII), Shanghai, China
Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions
Jul 15, 2026Anton V. Eremeev, Valentin A. TopchiiGenetic Algorithms Escape
Nonlinear Axiomatic Attribution for Cooperative Games
Jul 10, 2026Weida Li, Zhuanghua Liu, Yaoliang Yu +1Shapley Value Optimal
Department of Computer Science, National University of Singapore, Republic of Singapore · School of Computer Science, University of Waterloo, Canada · Vector Institute, Canada
Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning
Jun 18, 2026Ananya Kunisetty, Avishek GhoshOptimal Regret Matching Markets
Indian Institute of Technology Bombay, Mumbai 400076, India
Duality for Optimal Multi-Item, Multi-Bidder Auction Design: Revenue Certificates through Deep Learning
Jun 8, 2026Yanchen Jiang, David C. Parkes, Tonghan WangFirst-Price Auctions Primal-Dual Methods
Harvard University, USA · College of AI, Tsinghua University, China
Combinatorial Landscape Analysis for Dominating Set and Vertex Coloring
Jun 5, 2026Johanna Gasse, Antonia Heinen, Felix Knöfel +2Optimization Landscape Maximum Independent Set
Hasso Plattner Institute, Potsdam, Germany
GPTQ-intrinsic LoRA: A Near-optimal Algorithm for Low-precision Quantization with Low-rank Adaptation
May 31, 2026Shihao Zhang, Rayan SaabPost-Training Quantization Low-Rank Structure
Department of Mathematics, University of California San Diego
From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$ -Sparse GLMs
May 21, 2026Jiachang Liu, Andrea LodiSolvers Optimal
∗Center for Data Science for Enterprise and Society, Cornell University, Ithaca, USA · †School of Operations Research and Information Engineering, Cornell University, Ithaca, USA · ‡Jacobs Technion-Cornell Institute, Cornell Tech and Technion–IIT, New York, USA
Self-Distillation is Optimal Among Spectral Shrinkage Estimators in Spiked Covariance Models
May 18, 2026Radu Lecoiu, Debarghya Mukherjee, Pragya SurCovariance Self-Distillation Framework
Department of Statistics, Harvard University · Department of Mathematics & Statistics, Boston University
Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding
May 15, 2026Ning Zhou, Nikolai W. F. Bode, Edmund R. HuntMulti-Agent Path Finding Multi-Robot Systems
University of Bristol
Optimal Pattern Detection Tree for Symbolic Rule-Based Classification
May 14, 2026Young-Chae Hong, Yangho ChenDecision Trees Data Mining
Amazon Seattle, USA
Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning
May 8, 2026Michael Mancini, Shabnam SodagariQuantum Approximate Optimization Algorithm Optimal
Computer Engineering & Computer Science, California State University, Long Beach, CA 90840
Exploring the non-convexity in machine learning using quantum-inspired optimization
May 8, 2026Kandula Eswara Sai Kumar, Parth Dhananjay Danve, Abhishek Chopra +1Quantum Annealing Nonconvex
1*BosonQ Psi (BQP), New York, USA.
SLAM as a Stochastic Control Problem with Partial Information: Optimal Solutions and Rigorous Approximations
Apr 23, 2026Ilir Gusija, Fady Alajaji, Serdar YükselSimultaneous Localization And Mapping Partially Observable Markov Decision Process
Department of Mathematics and Statistics, Queen’s University, Kingston, ON, Canada
Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration
Apr 19, 2026Donghwan LeeBellman Equation Convergence
Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon 34141, South Korea
Stein Variational Black-Box Combinatorial Optimization
Apr 17, 2026Thomas Landais, Olivier Goudet, Adrien Goëffon +2Black-Box Optimization Stochastic Optimization
LERIA, Université d’Angers, 2 Boulevard Lavoisier, Angers 49045, France
Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem
Apr 17, 2026Srikar Gouru, Ariel Felner, Jiaoyang LiPath Planning Optimal
Carnegie Mellon University · Ben-Gurion University of the Negev
Variable Search Stepsize for Randomized Local Search in Multi-Objective Combinatorial Optimization
Feb 5, 2026Xuepeng Ren, Maocai Wang, Guangming Dai +4Large Neighborhood Search Combinatorial Optimization
School of Computer, China University of Geosciences, Engineering Research Center of Natural Resource Information Management and Digital Twin Engineering Software, Ministry of Education, and Hubei Key Laboratory of Intelligent Geo-Information Processing, Wuhan 430074, China · School of Computer, Science and Informatics, De Montfort University, Leicester LE1 9BH, U.K. · School of Computer Science, University of Birmingham, Birmingham B15 2TT, U.K. +1
Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms
Apr 4, 2024Miao Lu, Han Zhong, Tong Zhang +1Distributional Reinforcement Learning Offline Reinforcement Learning
†Department of Management Science and Engineering, Stanford University. · ‡Center for Data Science, Peking University. · §Department of Computer Science, University of Illinois Urbana-Champaign.
Silver Rate Is (Almost) Optimal for Gradient Descent
Date pendingYuhan Ye, Kaizhao LiuStep Accuracy Gradient Descent
MIT
Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch-and-Price
Date pendingAnoop Bhat, Geordan Gutow, David Neiman +4Vehicle Routing Problem Shortest Paths
Robotics Institute at Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213 · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · Robotics and AI Institute, Cambridge, MA 02142 +2

Oct 1, 2026, cs.LGJ/K move · Enter open · S save

Rate-Optimal Algorithm for Adversarial Linear CMDPs

Kihyun Yu, Honghao Wei, Dabeen Lee

KAIST · Washington State University · Seoul National University

Markov Decision Processes Primal-Dual Methods Partially Observable Markov Decision Process Optimal Adversarial Training

Open paper AskPDF arXiv

We study episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions, where both the loss and constraint functions may vary adversarially across episodes. The best previous algorithm achieves

\widetilde{\mathcal{O}}(K^{3/4})

regret and cumulative constraint violation, leaving a gap to the optimal

\widetilde{\mathcal{O}}(\sqrt{K})

dependence on the number of episodes

K

. We close this gap by proposing a new primal dual algorithm that achieves

\widetilde{\mathcal{O}}(\sqrt{K})

regret and cumulative constraint violation without assuming Slater's condition. We further extend the algorithm to achieve the same

\widetilde{\mathcal{O}}(\sqrt{K})

guarantees for regret and hard constraint violation, which does not allow constraint violations to cancel across episodes. The main challenge is that learning linear CMDPs requires uniform concentration over a value function class with a controlled covering number, whereas standard techniques in constrained online learning, such as policy mixing, can make this class more complex. Our algorithm combines adaptive Follow the Regularized Leader (FTRL), contracted value estimation, and an exponential Lyapunov function. An adaptive dual regularizer offsets the dependence on the dual weights in the primal regret bound, removing the need for policy mixing. We further show that the normalization in the FTRL update bounds the policy parameters independently of the magnitudes of the dual weights, which explains why the resulting policy class remains compatible with uniform concentration. Under feature access, the computational complexity is independent of the size of the state space.

Momentum

Related topics

Latest papers 36