Regret Minimization in RL

RL: Reinforcement Learning

Follow this topic Ask about this topic

Momentum

2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 29

All topics

Reinforcement Learning with Segment Reward Feedback under Linear Function Approximation
Oct 6, 2026Fengxu Liu, Siwei Wang, Gal Dalal +2Regret Minimization in RL Reinforcement Learning
National University of Singapore. · Microsoft Research Asia. · NVIDIA Research. +2
Rate-Optimal Algorithm for Adversarial Linear CMDPs
Oct 1, 2026Kihyun Yu, Honghao Wei, Dabeen LeeRegret Minimization in RL Markov Decision Processes
KAIST · Washington State University · Seoul National University
Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation
Sep 30, 2026Kihyun Yu, Seoungbin Bae, Dabeen LeeRegret Minimization in RL Markov Decision Processes
KAIST · Seoul National University
Decentralized Multi-Player Q-Learning in Episodic Markov Decision Processes with Information Asymmetry
Aug 13, 2026Larissa Xu, King Bi, William ChangRegret Minimization in RL Reinforcement Learning
Department of Mathematics University of California, Los Angeles Los Angeles, USA · Department of Computer Science University of California, Los Angeles Los Angeles, USA
Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning
Aug 7, 2026Ibne Farabi Shihab, Abu Sa-Adat Mohamed Moon-Im Al Ahsan, Md Najmus SwaqeebRegret Minimization in RL Markov Decision Processes
Department of Computer Science, Iowa State University · Department of Computer Science & Engineering, BRAC University
Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment
Jul 31, 2026Yanwei Jia, Du OuyangMulti-Armed Bandits Regret Minimization in RL
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong SAR · Department of Mathematical Sciences, Tsinghua University, Beijing, Beijing 100084, China
A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics
Jul 28, 2026Zheshun Wu, Renjie Zheng, Jinhang Zuo +2Non-Stationary RL Regret Minimization in RL
Southern University of Science and Technology · Harbin Institute of Technology, Shenzhen Shenzhen, Guangdong, China · Southern University of Science and Technology Shenzhen, Guangdong, China +4
Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
Jul 22, 2026Runlong Zhou, Zihan Zhang, Maryam Fazel +1Regret Minimization in RL Markov Decision Processes
University of Washington. · Hong Kong University of Science and Technology. · §University of Washington. +1
Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions
Jun 30, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RL Markov Decision Processes
Department of Mathematical Informatics, The University of Tokyo · Center for Advanced Intelligence Project, RIKEN
Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning
Jun 18, 2026Asaf Cassel, Aviv RosenbergRegret Minimization in RL Reinforcement Learning
Google Research
A Regret Minimization Framework on Preference Learning in Large Language Models
Jun 8, 2026Suhwan Kim, Taehyun Cho, Geon-Hyeong Kim +4Regret Minimization in RL LLM Alignment
Seoul National University, Seoul, South Korea · LG AI Research, Seoul, South Korea · UNIST, Ulsan, South Korea +1
Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification
Jun 4, 2026Haoyang Hong, Zichen Wang, Quanquan Gu +1Regret Minimization in RL Reinforcement Learning
School of Electrical Engineering and Computer Science, Oregon State University · Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illinois Urbana-Champaign · Department of Computer Science, University of California, Los Angeles
Minimax-Optimal Policy Regret in Partially Observable Markov Games
Jun 1, 2026Raman AroraRegret Minimization in RL Imperfect-Information Games
Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA.
Information-Directed Offline-to-Online Reinforcement Learning
May 28, 2026Keru ChenRegret Minimization in RL Bayesian RL
School of Electrical, Computer and Energy Engineering, Arizona State University
Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation
May 27, 2026Wonyoung Kim, Min-Hwan Oh, Garud Iyengar +1Regret Minimization in RL Reinforcement Learning
Chung-Ang University · Seoul National University · Columbia University
Learning Kernel-Based MDPs from Episodic Preferential Feedback
May 22, 2026Nikola Pavlovic, Sattar Vakili, Qing ZhaoPairwise Preference Learning Regret Minimization in RL
Cornell University · MediaTek Research
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
May 19, 2026Pierre Boudart, Pierre Gaillard, Alessandro RudiRegret Minimization in RL Markov Decision Processes
SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3
Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
May 15, 2026Zijun Chen, Zihan ZhangRegret Minimization in RL Reinforcement Learning
Department of Computer Science and Engineering Hong Kong University of Science and Technology
Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
May 12, 2026Kihyun Yu, Beomhan Baek, Dabeen LeeRegret Minimization in RL Markov Decision Processes
1KAIST · 2Seoul National University
Towards Differentially Private Reinforcement Learning with General Function Approximation
May 7, 2026Yi He, Xingyu ZhouRegret Minimization in RL Reinforcement Learning
Wayne State University, Detroit, USA
Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
May 6, 2026Harin Lee, Min-hwan OhMulti-Armed Bandits Regret Minimization in RL
University of Washington · Seoul National University
Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
May 1, 2026Haichen Hu, Jian Qian, David Simchi-LeviRegret Minimization in RL Markov Decision Processes
Laboratory for Information and Decision Systems · Department of AI and Data Science
Wasserstein Distributionally Robust Regret Optimization for Reinforcement Learning from Human Feedback
Apr 30, 2026Yikai Wang, Shang Liu, Jose BlanchetRegret Minimization in RL Reinforcement Learning
Department of Statistics and Operations Research, University of North Carolina · Imperial Business School, Imperial College London · Department of Management Science and Engineering, Stanford University
DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees
Apr 17, 2026Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. VeeravalliNon-Stationary RL Regret Minimization in RL
ECE and CSL, The Grainger College of Engineering University of Illinois at Urbana-Champaign
Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces
Mar 9, 2026Hamish Flynn, Joe Watson, Ingmar Posner +1RL Control Regret Minimization in RL
Carnegie Mellon University · University of Oxford · Technical University of Darmstadt +2
Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
Feb 2, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RL Markov Decision Processes
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · RIKEN AIP, Tokyo, Japan
Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
Sep 22, 2024Jia Wan, Sean R. Sinclair, Devavrat Shah +1Regret Minimization in RL Markov Decision Processes
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology · Department of Industrial Engineering and Management Sciences, Northwestern University
Thompson Sampling for Infinite-Horizon Discounted Decision Processes
May 14, 2024Daniel Adelman, Cagla Keceli, Alba V. Olivares-NadalThompson Sampling Regret Minimization in RL
Booth School of Business, The University of Chicago, Chicago, IL 60637, USA · United Airlines, Chicago, IL 60605, USA · UNSW Business School, UNSW, Kensington NSW 2033, Australia
Safe Learning Under Irreversible Dynamics via Asking for Help
Date pendingBenjamin Plaut, Juan Liévano-Karim, Hanlin Zhu +1Regret Minimization in RL Reinforcement Learning
Division of Computer Science University of California Berkeley, CA 94720-1776, USA

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

Reinforcement Learning with Segment Reward Feedback under Linear Function Approximation

Fengxu Liu, Siwei Wang, Gal Dalal, Shie Mannor+1

National University of Singapore. · Microsoft Research Asia. · NVIDIA Research.+2

Regret Minimization in RL Reinforcement Learning

Open paper AskPDF arXiv

Classical reinforcement learning (RL) assumes that a reward is observed for every visited state-action pair. However, in real-world applications such as autonomous driving, such fine-grained feedback can be costly or difficult to collect, whereas trajectory-level feedback may be too sparse for efficient learning. To provide a general feedback model bridging these two extremes and handle large state spaces, we study RL with segment reward feedback under linear function approximation. Our work answers how the granularity of segment feedback and the choice of segmentation influence learning. For equal-length segments with known transitions, we design algorithms

\bitssegd

and

\edlinucbsegd

for binary and sum feedback types, respectively. They adopt posterior sampling with planning to achieve computational efficiency and the E-optimal experimental design to attain near-optimality. Nearly matching lower bounds are established. For equal-length segments with unknown transitions, we develop a unified

\seglsvits

framework with two instantiations for binary and sum feedback, which carefully integrates the posterior estimated reward parameters into least-squares value iteration. These results reveal a fundamental insight: under binary feedback, increasing the number of segments significantly reduces the regret through an exponential factor, while surprisingly, under sum feedback, the granularity of segments does not affect learning much. Finally, to investigate whether segmenting according to state-action features can further expedite learning, we design an algorithm

\uneqsegbitsd

that allows arbitrary segmentations. The resulting regret bound shows that under the usual elliptical potential analysis, the influence of state-action features on the regret appears only through logarithmic factors, and equal segmentation achieves the best performance.

Momentum

Related topics

Latest papers 29