1.2Coordination

5 min read

By the end of this section you can answer

Why is a shared objective not enough to produce coordinated actions?

Coordination is the problem of learning individual actions whose combination advances a shared objective.

In this section you will

• Explain why aligned objectives do not imply compatible actions
• Read joint-action dependence off a small payoff table
• Define a joint-action value and say what it is a function of

Aligned Objectives and Interdependent Actions

Two agents in a kitchen. When an order is served, both receive the same payment. Neither can earn anything alone.

The simplest coordination problem there is. Same reward, same goal, separate decisions.

Formally, this is a common-reward game: every agent has the same reward function, so the team’s interests are identical by construction.

Figure 1

$$\tone{reward}{R_1} = \tone{reward}{R_2} = \cdots = \tone{reward}{R_\nag} = \tone{reward}{R}$$

$R_\ag$

agent i’s reward function

$R$

the single function they all share

Identical reward functions. There is nothing left for the agents to disagree about.

You would think that settles it. If everybody wants the same thing, and nothing anybody does can help themselves at another’s expense, what is left to go wrong?

Almost everything.

Key takeaway

Having the same objective does not tell the agents which actions they should take together.

The reward says what counts as success. It says nothing about who does which part.

The textbook version of this makes it unmissable. Albrecht, Christianos and Schäfer use a coordination game in which two agents receive a positive reward only when their actions agree, and nothing tells either agent which of the matching options to pick. Both agents want to agree. Wanting it does not make it happen.

Joint-Action Dependence

Back to the kitchen, and to what actually arrives at the environment.

Figure 2

$$\tone{action}{\jointact} = \bigl(\tone{policy}{\act{1}},\ \dots,\ \tone{policy}{\act{\nag}}\bigr)$$

$\jointact$

the joint action: what the team did this step

$\act{i}$

one agent’s contribution to it, chosen from local information

The environment sees the combination, never the parts.

Four possibilities at one step, with the same two agents and the same shared reward:

Agent 1	Agent 2	Team outcome
get ingredient	prepare station	both halves of the next step are ready
get ingredient	get ingredient	two trips for one ingredient
prepare station	prepare station	the station is prepared twice
wait	wait	nothing happens

Every one of those rows involves two agents who want an order served. Rows two and three are agents doing genuinely useful things, preparing a station is not a mistake, that happen to be the same useful thing at the same moment. Row four is two agents each sensibly waiting for the other to commit.

None of this is bad behaviour. It is uncoordinated behaviour, which is a different thing and the whole subject of this chapter.

Joint-Action Values

Now the formal consequence, and it is the piece worth carrying forward.

In single-agent reinforcement learning you can ask how good an action is in a state, and write the answer down as $Q(s, a)$. Try that here.

Figure 3

$$\dbox{conflict}{Q(\tone{observe}{s}, \tone{action}{a^{1}})} \qquad\text{versus}\qquad \cbox{action}{Q(\tone{observe}{s}, \tone{action}{a^{1}}, \tone{action}{a^{2}})}$$

$Q(s, a^{1})$

an individual action value: how good agent 1’s action is, with agent 2’s action left out

$Q(s, a^{1}, a^{2})$

a joint-action value: how good this combination is

The dashed form has to average away the very thing that decides the outcome. The solid form can tell the combinations apart.

The left-hand form cannot represent the kitchen table above. “Get ingredient” appears in row one, where it is excellent, and row two, where it is wasted. Any single number attached to “get ingredient” has to be some average across what agent 2 might do, and that average is not the value of anything the agent can actually bring about.

The right-hand form has room for the distinction. Give it both actions and it can say that (get, prepare) is worth a lot and (get, get) is worth little.

Key takeaway

An individual action value can hide the effect of another agent’s action. A joint-action value can represent different outcomes for different combinations.

That is the sentence the rest of the chapter is built on. Everything from centralized critics to value decomposition is a way of getting some of the right-hand form’s information without paying its full cost.

And the cost is real: $Q(s, \jointact)$ has an entry for every joint action, so it grows exponentially in the number of agents, and, worse for our purposes, an agent choosing from it would need to know what everybody else is about to do. Centralized and Decentralized Learning takes that problem seriously.

Knowledge check

An order has just arrived and the ingredient store is full. Is 'get ingredient' a good action for agent 1?

Select one answer.

AThere is not enough information. It depends on what agent 2 does at the same step.BYes. The order needs an ingredient and none has been collected.CNo. Agent 1 should wait to see what agent 2 does first.DYes, as long as agent 1’s policy is well trained.

Check answer

Coordination Summary

• A common-reward game gives every agent the same reward function. Their objectives are identical by construction.
• Identical objectives do not produce coordinated actions. Agents can want the same outcome and still duplicate work, interfere, or both wait.
• Poor coordination is usually not bad behaviour. It is two sensible choices that do not fit together.
• An individual action value $Q(s, a^\ag)$ must average over what partners do, hiding the effect that decides the outcome.
• A joint-action value $Q(s, \jointact)$ can distinguish combinations, at a cost in size, and in information no single agent has.