Games

Normal-Form Game

Normal-for game (or strategic-form) defines a single interaction between two or more agents.

Mathematically,

[!definition] A normal-form game consists of:

• Agents (Players): Finite set of agents $I = \{1, \dots, n\}$
• Actions: For each agent $i \in I$:
  • Finite set of actions $A_i$
  • Reward function $\mathcal{R}_i : A \rightarrow \mathbb{R}$, where $A = A_1 \times \dots \times A_n$

[!quote-yellow] Cartesian Product $A_1 = \{a, b\}$ > $A_2 = \{x, y\}$ > $A = A1 \times A2 = \{(a, x), (a, y), (b, x), (b, y)\}$ A is the space of joint action, tells all the possible ways players’ choices can line up together.

Game Procedure

• Each agent $i \in I$ selects a policy $\pi_i : A_i \rightarrow [0, 1]$. And, assigns probabilities to the actions available to the agent, so that $\sum_{a_i \in A_i}{\pi_i(a_i) = 1}$.
• Each agent samples an action $a_i \in A_i$ with probability $\pi_i(a_i)$ given by it's policy.
• The join action becomes, $a = (a_1, \dots a_n)$.
• Finally, each agent i receives a reward based on its reward function and joint action, $r = \mathcal{R}_i(a)$.

Stochastic Game

Stochastic games additionally define an environment state that can change in response to the agent's actions. Agents can see the full environment state and the previous action actions of all other agents.

[!definition] A stochastic game consists of:

• Agents (Players): Finite set of agents $I = \{1, \dots, n\}$
• States ($S$): Finite set of state $S$, with subset of terminal states $\bar{S} \subset S$
• Actions: For each agent $i \in I$:
  • Finite set of actions $A_i$
  • Reward function $\mathcal{R}_i : S \times A \times S \rightarrow \mathbb{R}$, where $A = A_1 \times \dots \times A_n$
• State transition probability function $\mathcal{T} : S \times A \times S \rightarrow [0, 1]$ such that $$\forall s \in S, a \in A: \sum_{s\prime \in S}{\mathcal{T}(s, a, s\prime) = 1}$$
• Initial state distribution $\mu : S \rightarrow [0, 1]$ such that $$\sum_{s \in S}{\mu(s)} = 1 \hspace{0.5em} and \hspace{0.5em} \forall s \in \bar{S}: \mu(s) = 0$$

Game Play

• Start at $s_0 \sim \mu$.
• At step $t$, agents choose joint action $a^t$.
• Transition: $s^{t+1} \sim T(s^t, a^t, \cdot)$.
• Rewards: $r_i^t = R^i(s^t, a^t, s^{t+1})$.

Follows Markov Property: $\Pr(s^{t+1}, r^t \mid s^t, a^t, s^{t-1}, a^{t-1}, \dots, s^0, a^0) = Pr(s^{t+1}, r^t \mid s^t, a^t)$

Partially Observable Stochastic Game (POSG)

[!definition] A partially observable stochastic game (POSG) extends a stochastic game with additional properties defined for each agent $i \in I$:

• Finite set of observations $O_i$
• Observation function $\mathcal{O}_i : A \times S \times O_i \rightarrow [0,1]$ such that $$\forall a \in A, s \in S: \sum_{o_i \in O_i}{\mathcal{O}_i(a, s, o_i)} = 1$$

History of agent $i$: $h_i^t = (o_i^0, \dots, o_i^t)$ Policy: $\pi_i (a_i^t \mid h_i^t)$