mlsanityData to 7 Oct 2026

Offline congestion games: How feedback type affects data coverage requirement

arXiv 2210.13396 ↗First posted 24 Oct 2022cs.GT cs.LG cs.MAcited by 1

Not on the map. Why?

Abstract (arXiv)

This paper investigates when one can efficiently recover an approximate Nash Equilibrium (NE) in offline congestion games. The existing dataset coverage assumption in offline general-sum games inevitably incurs a dependency on the number of actions, which can be exponentially large in congestion games. We consider three different types of feedback with decreasing revealed information. Starting from the facility-level (a.k.a., semi-bandit) feedback, we propose a novel one-unit deviation coverage condition and give a pessimism-type algorithm that can recover an approximate NE. For the agent-level (a.k.a., bandit) feedback setting, interestingly, we show the one-unit deviation coverage condition is not sufficient. On the other hand, we convert the game to multi-agent linear bandits and show that with a generalized data coverage assumption in offline linear bandits, we can efficiently recover the approximate NE. Lastly, we consider a novel type of feedback, the game-level feedback where only the total reward from all agents is revealed. Again, we show the coverage assumption for the agent-level feedback setting is insufficient in the game-level feedback setting, and with a stronger version of the data coverage assumption for linear bandits, we can recover an approximate NE. Together, our results constitute the first study of offline congestion games and imply formal separations between different types of feedback.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 19 of its 42 references that are in the map. First posted on arXiv 24 Oct 2022.

Builds on

19 of 42 references.

References · 19

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  3. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  5. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  7. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  8. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  9. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  10. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  11. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  12. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
7 more
  1. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 30
  2. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  3. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  4. 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13
  5. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  6. 2021Robustness and sample complexity of model-based MARL for general-sum Markov gamescited by 6
  7. 2016Generalized Mirror Descents in Congestion Gamescited by 5

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Learning Optimal Tax Design in Nonatomic Congestion Gamescited by 1