nucleation

LIT-1511: Frequency adjusted multi-agent Q-learning

2 min read

Properties4
StatusActive — read in full 2026-10-24 (NOTE-1140) from the AAMAS 2010 proceedings PDF on the IFAAMAS site; read in place of Tuyls, Verbeeck & Lenaerts 2003 (LIT-1501), whose model it restates and corrects. Worth reading as the correction to "Q-learning is replicator dynamics plus mutation": the selection–mutation equation describes Q-learning with Boltzmann exploration only if every action's estimate is updated at the same rate. In Q-learning the chosen action is updated more often, so the expected change of Q_i carries a factor x_i, and the learning traces depart from the model, depending on how the Q-values are initialized. Frequency Adjusted Q-learning divides the step by x_i and matches the model. Evidence is three 2×2 games, plotted, with no quantitative measure of fit.
Tagsgame-theory, learning-theory, anthology-candidate
Cited as “paper” byNOTE-1140 — Kaisers & Tuyls — Frequency adjusted multi-agent Q-learning
Cited as “source” byTHEORY-1234 — The replicator-plus-entropy model of Boltzmann Q-learning in two-player stateless games is exact for frequency-adjusted Q-learning, not for Q-learning, whose expected update carries an extra factor of each action's selection probability and whose trajectories in 2×2 games depart from the model depending on initialization, THEORY-932 — The replicator-plus-entropy model of Boltzmann Q-learning in two-player stateless games is, in the small-step limit, the expected dynamics of a learner that updates every action's value each step, and so of frequency-adjusted Q-learning wherever every action's probability is at least its adjustment parameter; it is not that of Q-learning, whose expected update carries an extra factor of each action's selection probability, so that its policy dynamics depend on the Q-values; in Kaisers and Tuyls's three 2×2 games at one temperature, compared by eye, Q-learning's trajectories departed from the model depending on initialization and the frequency-adjusted learner's followed it

Graph View

Kaisers, M. & Tuyls, K. (2010). Frequency adjusted multi-agent Q-learning. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), 309–315. IFAAMAS. doi:10.65109/vlue9705.

Key takeaways

From the reading, NOTE-1140. Page numbers are the proceedings’.

  • The model restated. Tuyls et al.’s dynamics for two-player stateless Boltzmann Q-learning are a replicator (selection) part plus a mutation part, −log x_i + Σ_k x_k log x_k (Eq. 2, p. 311).
  • The model is not Q-learning’s. The derivation assumes Q̇_i = α(E[r_i] + γ max_j Q_j − Q_i) for every action. Q-learning updates only the action taken, so E[Q̇_i] is x_i times that. “In essence, Q-learning fails to comply with its prediction because actions are updated at different frequencies” (p. 310).
  • What goes wrong. Over-estimated values of a frequently chosen dominant action are corrected faster, so Q-learning can move away from a dominant action, and its path depends on the initial Q-values, which a policy-space model cannot represent (pp. 312–313).
  • The fix. FAQ-learning scales each update by min(β/x_i, 1). In the small-α limit it is the model wherever x_i ≥ β (THEORY-932).

Why this is here

Filed 2026-10-24, when the owner asked how the record stands on multi-agent reinforcement learning, in place of LIT-1501. It corrects the description “Q-learning is replicator dynamics plus an exploration term”: that equation is exact for learners that update every option’s estimate at the same rate, as Sato and Crutchfield’s learners do (LIT-1520). It carries anthology-candidate because FAQ-learning is an algorithm. It is filed for what it shows about learning dynamics, not as an instruction for practice.

Backlinks