Foundations — Multi-agent reinforcement learning

Before you can read a single line of the parent note, you must be able to see what each squiggle means. We go one symbol at a time. Nothing is used before it is drawn.

0. The picture we are always inside

Everything in RL is one loop: an agent looks at the world, does something, the world changes and hands back a number. Hold this picture — every symbol below is a label on some part of it.

We need these three because RL has exactly one goal: choose actions that make the stream of reward numbers as large as possible.

1. State $\mathcal{S}$ and $s$ — "the current situation"

• Symbol: $s\in \mathcal{S}$ reads "$s$ is one element of the set $\mathcal{S}$." The symbol $\in$ just means "is inside this bag of possibilities."
• Picture: in the figure above, $s$ is the label on the box "board position." $\mathcal{S}$ is the whole collection of every board you could ever see.
• Why the topic needs it: the world's response depends on which situation you are in. No state → no way to say "in situation A do X, in situation B do Y."

2. Action $\mathcal{A}$ and $a$ — "what you can do"

• Symbol: $a\in \mathcal{A}$. Same $\in$ idea.
• Superscript vs subscript: later we write $a^i$ — the little raised $i$ means "the action belonging to agent number $i$." A raised index labels whose it is. Remember this; the whole multi-agent story rides on it.
• Picture: the arrow leaving the agent in the loop figure.
• Why: learning = discovering which action is best in each state.

3. Policy $\pi$ — "your strategy, as a rule"

• Picture: a lookup card. State goes in the top; the card tells you what to do.

• Why two flavours? Some games (Rock–Paper–Scissors) require randomness or you get exploited — those need $\pi (a\mid s)$. Some methods (MADDPG in the parent) use a single fixed action per state — those use $\mu (s)$.
• Why the topic needs it: the whole point of MARL is that every agent has its own policy ${\pi }^i$, and they all change while learning. That changing is the villain of the story.

4. Transition $P(s^{\prime }\mid s,a)$ — "how the world moves"

• The prime mark ${}^{\prime }$: $s^{\prime }$ just means "the state after." Prime = next.
• Picture: a branching fan — from $(s,a)$ several arrows fan out to possible next states, each with a probability.
• Why "probability" and not a fixed next state? Because the world can be noisy: same action, different outcomes (dice, wind, opponent). Probabilities cover all cases at once.

5. Discount $\gamma$ — "sooner reward is worth more"

• Why $[0,1)$ and not $[0,1]$? The square bracket $[$ includes $0$; the round bracket $)$ excludes $1$. We must keep $\gamma <1$ so an infinite stream of rewards adds to a finite number (a geometric series $1+\gamma +{\gamma }^2+\cdots =\frac{1}{1-\gamma }$ only converges when $\gamma <1$). At $\gamma =0$ you are greedy — only the next reward matters.
• Picture: rewards fading into the distance like poles shrinking down a road.

6. Return and Value $V$ — "total future score"

• The $\mathbb{E}[\cdot ]$ symbol: "expected value" = the average outcome, weighting each possibility by how likely it is. We need it because rewards are random (Section 4), so we ask for the average total, not one lucky run.
• Why value, not just reward? A single reward is myopic. Value answers the real question: "how good is being here, counting everything that follows?"
• The subscript $\pi$ in $V_{\pi }$: value always depends on which strategy you follow. Change the policy, change the value.

7. Action-value $Q(s,a)$ — "how good is this move here"

• Why we need Q on top of V: to choose, you compare actions. $Q$ lets you say "action $a_1$ scores 5, $a_2$ scores 3, pick $a_1$." That comparison is the heart of Q-Learning.
• The $\arg \max$ symbol: $\arg {\max }_{a}Q(s,a)$ means "the action that gives the biggest $Q$." Note: $\max$ returns the biggest value; $\arg \max$ returns the input (action) that achieves it. In MARL this distinction matters (QMIX in the parent is all about matching argmaxes).

8. From one agent to many: the index $i$ and $-i$

Now the multi-agent jump. Every symbol above gets a raised label saying whose it is.

• Picture: a row of players. Highlight one as $i$; the rest of the row is the crowd $-i$.

• Why the joint action? Because in MARL the world's transition $P(s^{\prime }\mid s,\mathbf{a})$ and every reward $r^i(s,\mathbf{a})$ depend on everyone's move at once. Your reward is not yours to control alone — that single fact creates the whole field.
• The $\prod$ symbol: ${\prod }_{j\ne i}$ means "multiply together over all agents $j$ that are not $i$." It shows up because independent players' probabilities multiply. It's the many-agent cousin of $\sum$ (which adds).

9. The vocabulary that names the whole setup

• Why "stochastic"? Stochastic just means "involving randomness" — the transitions and policies use probabilities.

Prerequisite map

Each foundation box on the left is something you must already see clearly; they flow rightward and merge into the parent topic.

Equipment checklist

Test yourself — cover the right side. If any answer is fuzzy, re-read that section before opening the parent note.

Related: Multi-agent reinforcement learning · Markov Decision Process · Q-Learning · Policy Gradient Methods · Actor-Critic Methods · Game Theory & Nash Equilibrium · Self-Play