# Friend or Foe Q Learning Algorithm Q-Value Update

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.

$\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.
• Ok, I think that makes sense. So where is the $\pi$ probability distribution coming from? Is it just a matter of observing what actions are taken by other agents in specific states and assigning probabilities based on how frequently actions come up? Commented Jul 13, 2015 at 13:19
• Ahhh ok, so it would be like assigning a 1 - $\epsilon$ probability to the greatest value and a $\epsilon$ probability to everything else (in the case of an $\epsilon$-greedy policy). Commented Jul 13, 2015 at 15:41