Episodic RL

RL: Reinforcement Learning

Follow this topic Ask about this topic

Latest papers

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

Improved regret bounds in tabular RL under local differential privacy
Nov 2, 2026Hugo RichardRegret Minimization in RL Tabular RL
ENSAE, FAIRPLAY
Closing the Log Gap: Minimax-Optimal Regret for Episodic RL
Oct 29, 2026Guy Zamir, Victor Boone, Matthew Zurek +1Episodic RL Reinforcement Learning
Department of Computer Sciences, University of Wisconsin–Madison · IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France
Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
Sep 19, 2026Kenny Guo, Valentio Iverson, Sahan Wijetunga +1Markov Decision Processes Continuous-Time RL
Department of Economics, Yale University, New Haven, Connecticut, USA · Department of Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA · Department of Mathematics, University of California, Los Angeles, Los Angeles, California, USA
Decentralized Multi-Player Q-Learning in Episodic Markov Decision Processes with Information Asymmetry
Aug 13, 2026Larissa Xu, King Bi, William ChangEpisodic RL Regret Minimization in RL
Department of Mathematics University of California, Los Angeles Los Angeles, USA · Department of Computer Science University of California, Los Angeles Los Angeles, USA
Episodic Memory Temporal Consistency for Cooperative Multi-Agent Reinforcement Learning
Jun 3, 2026Zicheng Zhao, Yu Lan, Chengzhengxu Li +2Episodic RL Reinforcement Learning
Xi’an Jiaotong University · Queen Mary University of London
Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback
May 22, 2026Zitian Li, Wang Chi CheungReinforcement Learning RL Exploration
Department of Industrial Systems Engineering & Management National University of Singapore Engineering Drive 2 Block E1A #06-25 Singapore 117576
Remember to be Curious: Episodic Context and Persistent Worlds for 3D Exploration
May 21, 2026Lily Goli, Justin Kerr, Daniele Reda +3Episodic RL Reinforcement Learning
University of Toronto · Wayve · Vector Institute +2
ReversedQ: Opportunities for Faster Q-Learning in Episodic Online Reinforcement Learning
May 20, 2026Sofia R. Miskala-Dinc, Aviva PrinsEpisodic RL Reinforcement Learning
University of Maryland College Park, MD, United States
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
Extending Differential Temporal Difference Methods for Episodic Problems
May 6, 2026Kris De Asis, Mohamed Elsayed, Jiamin HeEpisodic RL Reinforcement Learning
1Openmind Research Institute · Department of Computing Science, University of Alberta, Canada · 3Alberta Machine Intelligence Institute (Amii)
Learning From Failures: Efficient Reinforcement Learning Control with Episodic Memory
Mar 7, 2026Chenyang MiaoEpisodic RL Reinforcement Learning
Xi’an Jiaotong University
Agentic Episodic Control
Jun 2, 2025Xidong Yang, Wenhao Li, Junjie Sheng +4Episodic RL Agentic RL
East China Normal University · Tongji University · Shanghai Jiao Tong University +2

Nov 2, 2026J/K move · Enter open · S save

Improved regret bounds in tabular RL under local differential privacy

Hugo Richard

ENSAE, FAIRPLAY

Regret Minimization in RL Tabular RL Episodic RL Differential Privacy

Open paper AskPDF arXiv

We study regret minimization for time-homogeneous episodic tabular reinforcement learning with

S

states and

A

actions under non-interactive

ε

-local differential privacy (LDP). In each episode

k \in [K]

, the decision-maker sends a policy to a user, the user executes the policy for

H

steps, and sends an

ε

-locally differentially private message back to the decision-maker. When

H=1

, the problem reduces to an LDP contextual bandit with

S

contexts,

A

arms and horizon

K

. We prove that the minimax regret is

\min\bigg(K, \frac{ \sqrt{\max( S, \exp(ε) + 1) S A K (\exp(ε) + 1)}}{\exp(ε) - 1}\bigg)

, up to constants and a

\sqrt{\log(A)}

factor. The upper bound is achieved by an adaptation of EXP3 and a unary encoding mechanism. When

H > 1

, and for small

ε

, we show a lower bound in

Ω(HS\frac{\sqrt{A K}}ε)

and an upper bound in

\tilde{O}(H^2 S^2 \frac{\sqrt{ AK}}ε)

. The upper bound is achieved by an algorithm based on UCBVI and a unary encoding mechanism. For small

ε

, these bounds improve the previously known lower bound by a factor

\sqrt{S}

and the previously known upper bound by a factor of

H \sqrt{A}