Research map / Bandits and online learning / RL theory and MDPs

Concurrent Reinforcement Learning with Aggregated States via Randomized Least Squares Value Iteration

ICML 2025 · Bandits and online learning › RL theory and MDPs · approach: Linear function approximation in RL · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes concurrent randomized least-squares value iteration (RLSVI) with aggregated states for N cooperating agents, giving worst-case regret bounds for finite- and infinite-horizon MDPs, with a variant that stores only the last episode/pseudo-episode.

Problem

Whether randomized value-function exploration (RLSVI) can be provably efficient when many agents explore one MDP concurrently and share data, in a model-free, memory-feasible way, under aggregated-state representations.

Approach

Adapts RLSVI to concurrent learning with aggregated states: each agent perturbs rewards with Gaussian noise and fits a regularized loss toward the previous episode's values, averaging across agents at episode end; a variant keeps only the last episode's data to cut space complexity by a factor of K at a sqrt(K) regret cost.

Key results

• Finite-horizon worst-case regret bound of Õ(εKHN + KH^{5/2}Γ√N) for the one-episode-storage variant, and Õ(εË√K HN + H^{5/2}Γ√(KN)) for the full-history variant.
• Per-agent regret decreases at rate Θ(1/√N) in both finite- and infinite-horizon settings, supported by experiments on synthetic MDPs with N from 1 to 50.
• Improves the H^{3/2}-type worst-case regret of prior single-agent RLSVI analysis by H^{1/2} for the single-agent case, giving Õ(H^2Γ√T).

Measured effects reported in the paper

Limitations

• Regret bounds carry an epsilon misspecification term from aggregation error.
• Full-history variant is space-infeasible for large N, so the practical algorithm has an extra sqrt(K) regret factor.
• Experiments are on small synthetic MDPs only, with no real-world benchmarks.

Experimental setup

Datasets: synthetic MDPs with Dirichlet transitions and uniform rewards

Benchmarks: synthetic MDPs (finite-horizon and infinite-horizon settings)

Metrics: worst-case per-agent regret per-agent regret scaling with number of agents N

Baselines: RLSVI (single-agent, all-history) concurrent PSRL concurrent LSVI

Builds on: RLSVI posterior sampling for reinforcement learning concurrent PSRL aggregated-state Q-learning

Closest papers by meaning

• Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration (AAAI 2021 · similarity 0.89)
• Generalization and Exploration via Randomized Value Functions (ICML 2016 · similarity 0.89)
• Randomized Exploration in Reinforcement Learning with General Value Function Approximation (ICML 2021 · similarity 0.89)
• Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.87)
• Position: Constants are Critical in Regret Bounds for Reinforcement Learning (ICML 2025 · similarity 0.87)
• Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.87)