The paper introduces Robust Fed-Q, a federated Q‑learning algorithm designed for settings where multiple agents interact with a shared Markov Decision Process and communicate through a central server. It combines model‑based and model‑free reinforcement learning techniques with a median‑of‑means strategy from robust statistics to handle a small fraction of adversarial agents. The authors prove that Robust Fed-Q achieves exact convergence to the optimal value function with high probability, attains near‑optimal finite‑time rates that benefit from collaboration, and requires only “~O(1)” communication rounds per guarantee.
By Sreejeet Maity, Aritra Mitra
arXiv:2607. 08012v1 Announce Type: cross Abstract: This paper studies an online variant of the assistance games framework, where an informed agent and an uninformed agent repeatedly interact over $T$ timesteps to optimize a common reward function.
By Nivasini Ananthakrishnan, Mark Bedaywi, Michael I. Jordan, Stuart Russell, Nika Haghtalab
The paper introduces Robust Async-Fed-Q, an epoch‑based federated Q‑learning algorithm that combines variance‑reduced Bellman operator estimation with robust server aggregation. It provides high‑probability finite‑time guarantees showing that honest agents retain sample‑efficiency benefits even when some agents act adversarially, with the adversarial impact diminishing as honest data grows. The authors also present matching lower bounds, extend the framework to single‑trajectory sampling and heterogeneous coverage, and improve communication complexity for asynchronous federated Q‑learning.
By Sreejeet Maity, Aritra Mitra
arXiv:2510. 02149v2 Announce Type: replace Abstract: We introduce Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs), a reinforcement learning framework for partial observability in which full state observations occur stochastically at each step, with probability determined by the chosen action.
By Alexander Ryabchenko, Wenlong Mou
The paper addresses policy optimization in online episodic tabular MDPs with adversarial losses and bandit feedback. By employing regularized Q‑functions, the authors eliminate the extra horizon factor present in previous policy‑optimization regret bounds, achieving high‑probability regret of ≥O(√{HS(H+A)T}) for known transitions and ≥O(HS√{AT}) for unknown transitions. These results improve horizon dependence and match the best-known bounds, with extensions to adversarial linear‑mixture MDPs.
By Mingyi Li, Taira Tsuchiya
The paper introduces PF‑LSA, a minimalist algorithm for personalized federated linear stochastic approximation that blends each agent’s local update with a global average. It achieves both fast convergence to each agent’s personalized solution and a linear speedup in the number of agents when their learning problems are similar, without requiring prior knowledge of heterogeneity. The analysis decomposes error into consensus and disagreement components, showing rapid decay of consensus error and negligible disagreement in low‑heterogeneity regimes.
By Safwan Labbi, Paul Mangold, Eric Moulines