State Uncertainty

Chapter 1: POMG Formalism

A partially observable Markov game (POMG) for n agents is (I, S, A₁, …, A_n, T, R₁, …, R_n, Ω₁, …, Ω_n, O, γ):

After each step, the world moves to s' ~ T(·|s,a). Each agent i receives a private observation o_i ~ O_i(·|s',a). Agent i's policy maps their observation history to an action: π_i : (o_i,1, a_i,1, …, o_i,t) → Δ(A_i). Note: agent i does not see the observations of other agents.

Chapter 2: Private Beliefs

In a POMDP, there's one belief state b(s) = P(s | o₁, a₁, …, o_t). In a POMG, each agent maintains their own private belief b_i(s) = P(s | o_i,1, a_i,1, …, o_i,t). Agent i conditions only on their own history, not the others'.

Agent i's belief update after taking action a_i and receiving observation o_i is a Bayesian update:

But wait — this update requires conditioning on the joint action a. Agent i knows their own action a_i, but must model the other agents' actions a_−i. Without knowing the others' policies, agent i must marginalize over their opponents' strategies to compute the update:

Chapter 3: Policy Evaluation

Given a joint policy (π₁, …, π_n), how do we compute each agent's expected value? In a fully observable Markov game, this was a system of linear equations. In a POMG, policies depend on observation histories, which grow exponentially — so we need a different approach.

For finite-horizon POMGs (T steps), we can evaluate a joint policy by unrolling the observation history tree. The joint observation history at time t is h_t = (a₁, o₁, …, a_t−1, o_t) where each o is a joint observation. The number of nodes in this tree is |A|^t|Ω|^t — exponential in t.

The expectation is over the joint stochastic process defined by T, O, and the policy π. We compute it by summing over all possible observation histories, weighting by their probability under the joint policy.

python
def evaluate_joint_policy(pomg, pi, b0, horizon):
    """Monte Carlo evaluation of joint policy pi in POMG.
    pomg: POMGame object (step, reward methods).
    pi: list of n policy functions pi[i](obs_history, action_history).
    b0: initial belief (distribution over states).
    Returns estimated value for each agent."""
    n = pomg.n_agents
    total_values = [0.0] * n
    n_rollouts = 200

    for _ in range(n_rollouts):
        s = pomg.sample_state(b0)  # sample initial state
        obs_hist = [[] for _ in range(n)]
        act_hist = [[] for _ in range(n)]
        discount = 1.0

        for t in range(horizon):
            # Each agent chooses action from their private history
            actions = [pi[i](obs_hist[i], act_hist[i]) for i in range(n)]
            # Step the environment
            sp, obs, rewards = pomg.step(s, actions)
            for i in range(n):
                total_values[i] += discount * rewards[i]
                obs_hist[i].append(obs[i])
                act_hist[i].append(actions[i])
            s = sp; discount *= pomg.gamma

    return [v / n_rollouts for v in total_values]

Chapter 4: Nash Equilibrium for POMGs

A joint policy (π₁*, …, π_n*) is a Nash equilibrium for a POMG if no agent can improve their expected value by unilaterally changing their behavioral policy, given the other agents' equilibrium policies:

Note: π_i here is a behavioral policy — it maps each possible private history to an action distribution. This is a much richer strategy space than normal form strategies (single probability vector) or Markov policies (state-indexed).

Chapter 5: Dynamic Programming

For finite-horizon POMGs, dynamic programming provides an exact backward induction algorithm. Starting from the last time step and working backwards, we compute the optimal behavioral strategies at each decision point.

Define the reachability of an observation history h under joint policy π and initial belief b₀. The backward induction computes, at each observation node, the Nash equilibrium of the stage game with continuation values as payoffs.

python
def backward_induction_pomg(pomg, b0, horizon):
    """Exact backward induction for finite-horizon 2-player POMG.
    Returns Nash equilibrium strategies and value."""
    def solve_node(belief, t, hist1, hist2):
        # Stage game payoffs: integrate over states weighted by belief
        U1 = np.zeros((pomg.nA1, pomg.nA2))
        U2 = np.zeros((pomg.nA1, pomg.nA2))
        for a1 in range(pomg.nA1):
            for a2 in range(pomg.nA2):
                for s, bs in enumerate(belief):
                    r1 = pomg.R1[s, a1, a2]; r2 = pomg.R2[s, a1, a2]
                    if t < horizon:
                        # Continuation: sum over next states and obs
                        for sp, o1, o2, prob in pomg.transitions(s, a1, a2):
                            b_next = pomg.belief_update(belief, a1, a2, o1, o2)
                            v1, v2, _, _ = solve_node(b_next, t+1, hist1+[o1], hist2+[o2])
                            r1 += pomg.gamma * prob * v1
                            r2 += pomg.gamma * prob * v2
                    U1[a1, a2] += bs * r1
                    U2[a1, a2] += bs * r2
        pi1, pi2 = solve_nash_2x2(U1, U2)
        v1 = pi1 @ U1 @ pi2; v2 = pi1 @ U2 @ pi2
        return v1, v2, pi1, pi2
    return solve_node(b0, 0, [], [])

Chapter 6: I-POMDPs

Instead of assuming agents reason to Nash equilibrium globally, Interactive POMDPs (I-POMDPs) (Gmytrasiewicz & Doshi, 2005) model agent i's planning as a POMDP where the state space includes the beliefs and intentions of other agents.

In an I-POMDP for agent i, the "augmented state" is (s, θ_−i) where s is the physical state and θ_−i is a model of each opponent j — specifically, j's type, including j's belief about the world and j's strategy.

Agent i maintains a belief over both the physical state and the opponent's type. When i observes (a_i, o_i), they update this joint belief using Bayes' rule. This is like a POMDP with an augmented state space S × Θ_−i.

Chapter 7: SHOWCASE — Pursuit Game

A pursuer (orange) tries to catch an evader (teal) in a grid. Both have noisy sensors — they observe approximate positions, not exact ones. This is a zero-sum POMG: the pursuer wants to minimize time to catch; the evader wants to maximize it.

Chapter 8: Approximations

Exact POMG solving is intractable for all but toy problems. The same approximation techniques from single-agent POMDPs (Ch 20–22) extend to the multiagent setting, often with reduced guarantees.

Chapter 9: Connections & Beyond

POMGs sit at the intersection of game theory and partially observable planning. The two key extensions from this chapter are Dec-POMDPs (Ch 27) for fully cooperative settings, and I-POMDPs for bounded-rationality opponent modeling.

"In the long run, it may turn out that partial observability is the most important aspect of multiagent systems — more important than the number of agents, more important than the reward structure."
— Paraphrase, Oliehoek & Amato, A Concise Introduction to Decentralized POMDPs (2016)