Friend or Foe Q Learning Algorithm Q-Value Update

Question

I'm trying to learn how to update the Q-values for FFQ (paper available here), but I'm stumbling over the notation and can't seem to figure out exactly what it wants me to do. From the paper:

$Q_i[s,a_1,...,a_n] := (1-\alpha)Q_i[s,a_1,...,a_n] + \alpha_t(r_i + \gamma Nash_i(s,Q_1,...,Q_n))$

is performed each time a new experience occurs, with the $Nash_i$ replaced with:

$Nash_i(s,Q_1,...,Q_n) = \max\limits_{\pi\in\Pi(X_1\times\cdots\times X_k)}\sum\limits_{x_1,...,x_k\in X_1\times\cdots\times X_k}\pi(x_1)\cdots\pi(x_k)Q_i[s,x_1,...,x_k].$

where $X_1$ through $X_k$ are the actions available to the $k$ friends of player $i$.

I'm not sure I understand the $Q_i[s,a_1,...,a_n]$. I was under the impression that using this approach would mean only one Q table for each learning agent, but does that table involve values for every possible combination of actions for all agents at a given state? Because that seems like it would become intractable very quickly. Also, I'm not sure what I'm looking for with $\pi(x_1)\cdots\pi(x_k)$. I know that $\pi$ is the policy for each agent, but what exactly is supposed to be returned?

Ideally I'd like to have a pseudo-code explanation of how this updating is supposed to work, but really any clarity would help me greatly.

Answer 1

In regular Q learning, Q is a table that has a row for every state and a column for every action. It seems that this approach adds another dimension to this table for the actions of every additional agent. You are right, this is not very practical.

$\pi$ is a probability distribution over the available actions. Multiplying the probabilities of actions for all your friends gives you the probability of that collective choice of actions — this will add up to 1 when summed over all combinations of actions. In effect the Nash probability calculates a weighted average of actions in the current state, where each action value is weighted by its probability under a choice of policy. The policy is chosen in such a way as to maximize this weighted average.

The paper also minimizes over the actions of foes. So, you choose foe actions that leave your friends with the smallest maximum Q, and then choose the friend actions that give you that Q value.

Maybe I misunderstand, but it seems like there would be a unique Q value that satisfies this condition, and the sum has only a single non-zero term.