Transition Dynamics

Why Does This Exist?

In idealized computing environments, taking an action produces a deterministic outcome: if you write a byte to memory, it lands in that memory address with certainty. Real physical systems and competitive environments rarely behave this predictably. A robot issuing a drive command may hit slippery ice, an autonomous car steering right can encounter sudden wind gusts or traction loss, a network router forwarding a packet may suffer buffer drops, and a trading algorithm submitting a market order faces slippage and stochastic order fills.

Without a formal mechanism for transition dynamics, decision algorithms assume deterministic transitions—that taking action $a$ in state $s$ always leads to a single known next state $s'$. Under this naive assumption, an agent designs brittle plans that catastrophic noise dismantles within milliseconds. Furthermore, foundational reinforcement learning frameworks—such as Markov Decision Processes, Bellman Equations, and Value Functions—cannot formulate expected returns without knowing how likely each outcome is.

Transition dynamics provide the exact mathematical engine that models environmental physics. By mapping each state-action pair $(s, a)$ to a rigorous probability distribution over all possible successor states $s'$, the dynamics function lets an agent compute expected returns, hedge against downside risks, and plan optimal behaviors in uncertain worlds.

Think of It Like This

How It Actually Works

The Conditional Dynamics Kernel and Joint Dynamics Function

In a Markov Decision Process, the environment's physics are formalized through conditional probability distributions. Let $\mathcal{S}$ denote the set of all valid states, $\mathcal{A}$ denote the set of all actions, and $\mathcal{R} \subset \mathbb{R}$ denote the set of possible rewards.

1. State Transition Probability Function

The standard state transition probability $P(s' \mid s, a)$ (often written as $T(s, a, s')$ or $\mathcal{P}_{ss'}^a$) defines the conditional probability that the environment transitions to state $s'$ at time $t+1$, given that the agent observed state $s$ and selected action $a$ at time $t$:

This formulation relies on the Markov Property: the transition distribution depends exclusively on the current state $S_t$ and immediate action $A_t$, making the full historical sequence of prior states and actions $(S_0, A_0, S_1, \dots, S_{t-1}, A_{t-1})$ conditionally independent:

2. The Four-Argument Joint Dynamics Function

In modern literature (notably Sutton & Barto), the environment is completely characterized by a four-argument joint dynamics function $p: \mathcal{S} \times \mathcal{R} \times \mathcal{S} \times \mathcal{A} \to [0, 1]$:

The state transition probability is recovered by marginalizing out the reward:

Similarly, the expected immediate reward received from taking action $a$ in state $s$ is the expectation across all possible rewards and successor states:

3. Row Stochasticity and Transition Matrices

Because $P(\cdot \mid s, a)$ represents a valid probability distribution over mutual events, it must satisfy the axioms of probability:

For a finite state space with $|\mathcal{S}| = n$, each action $a$ defines an $n \times n$ transition probability matrix $\mathbf{P}^a$:

Every row of $\mathbf{P}^a$ sums to exactly 1, making $\mathbf{P}^a$ a right-stochastic matrix. If the agent follows a fixed policy $\pi(a \mid s)$, the induced transition matrix $\mathbf{P}^\pi$ is:

Given an initial state probability distribution vector $\boldsymbol{\mu}_0 \in \mathbb{R}^{1 \times n}$, the state distribution at step $t$ evolves through vector-matrix multiplication:

Worked numerical example

Consider a 3-state stochastic corridor environment:

• $s_1$: Safe Road
• $s_2$: Icy Patch
• $s_3$: Goal Destination (absorbing terminal state)

The agent chooses action $a = \text{Forward}$. The transition dynamics matrix $\mathbf{P}^{\text{Forward}}$ is:

Row checks confirm row-stochasticity:

• Row 1: $0.10 + 0.70 + 0.20 = 1.00$
• Row 2: $0.20 + 0.30 + 0.50 = 1.00$
• Row 3: $0.00 + 0.00 + 1.00 = 1.00$

Step 1: Forward distribution propagation over time

Assume the agent starts with absolute certainty in $s_1$, giving initial state vector:

After 1 step, the state distribution $\boldsymbol{\mu}_1 = \boldsymbol{\mu}_0 \mathbf{P}^{\text{Forward}}$ is:

After 2 steps, the distribution $\boldsymbol{\mu}_2 = \boldsymbol{\mu}_1 \mathbf{P}^{\text{Forward}}$ becomes:

Notice that the sum $0.15 + 0.28 + 0.57 = 1.00$, preserving the total probability mass, with a 57% chance of already having reached the Goal.

Step 2: Weighting Bellman value expectations

Now let current state values be estimated as:

• $V(s_1) = 2.00$
• $V(s_2) = 5.00$
• $V(s_3) = 10.00$

Taking action $a = \text{Forward}$ from $s_1$ yields an immediate step reward $R(s_1, \text{Forward}) = -1.00$, with discount factor $\gamma = 0.90$. The expected successor state value is computed by weighting each possible future state by its transition probability:

The Bellman action-value is therefore:

Without the transition probabilities $0.10, 0.70, 0.20$, computing this expectation would be impossible.

Code

1import random2from typing import Dict, List, Tuple3
4
5class TransitionModel:6    """Represents an MDP transition dynamics kernel P(s' | s, a) with invariant verification."""7
8    def __init__(9        self,10        states: List[str],11        actions: List[str],12        transitions: Dict[Tuple[str, str], Dict[str, float]],13    ) -> None:14        self.states = states15        self.actions = actions16        self.transitions = transitions17        self._validate_stochasticity()18
19    def _validate_stochasticity(self, tolerance: float = 1e-6) -> None:20        """Verifies row-stochasticity: for every (s, a), sum_s' P(s'|s,a) == 1.0."""21        for s in self.states:22            for a in self.actions:23                dist = self.transitions.get((s, a), {})24                total_prob = sum(dist.values())25                if abs(total_prob - 1.0) > tolerance:26                    raise ValueError(27                        f"Row-stochasticity violated for ({s}, {a}): sum = {total_prob:.6f}"28                    )29                for s_prime, prob in dist.items():30                    if prob < 0.0 or prob > 1.0:31                        raise ValueError(32                            f"Invalid probability {prob} for transition ({s}, {a}) -> {s_prime}"33                        )34
35    def transition_matrix(self, action: str) -> List[List[float]]:36        """Constructs the square transition matrix P^a where entry (i, j) is P(s_j | s_i, a)."""37        return [38            [self.transitions[(s, action)].get(s_next, 0.0) for s_next in self.states]39            for s in self.states40        ]41
42    def sample_next_state(self, state: str, action: str, rng: random.Random) -> str:43        """Simulates environment physics by sampling s' ~ P(. | s, a)."""44        dist = self.transitions[(state, action)]45        candidates = list(dist.keys())46        weights = list(dist.values())47        return rng.choices(candidates, weights=weights, k=1)[0]48
49
50def propagate_distribution(51    distribution: List[float], transition_matrix: List[List[float]]52) -> List[float]:53    """Computes mu_{t+1} = mu_t @ P for a state distribution vector mu."""54    n_states = len(transition_matrix)55    return [56        sum(distribution[i] * transition_matrix[i][j] for i in range(n_states))57        for j in range(n_states)58    ]59
60
61if __name__ == "__main__":62    # Define states and actions for a 3-state icy corridor63    states = ["SafeRoad", "IcyPatch", "Goal"]64    actions = ["Forward"]65
66    # Dynamics mapping: (state, action) -> {next_state: probability}67    transitions = {68        ("SafeRoad", "Forward"): {"SafeRoad": 0.10, "IcyPatch": 0.70, "Goal": 0.20},69        ("IcyPatch", "Forward"): {"SafeRoad": 0.20, "IcyPatch": 0.30, "Goal": 0.50},70        ("Goal", "Forward"): {"SafeRoad": 0.00, "IcyPatch": 0.00, "Goal": 1.00},71    }72
73    env = TransitionModel(states, actions, transitions)74    p_mat = env.transition_matrix("Forward")75
76    # 1. Exact theoretical distribution evolution: mu_{t+1} = mu_t @ P77    mu_0 = [1.0, 0.0, 0.0]  # Agent begins in SafeRoad with certainty78    print("Initial distribution (t=0):", [round(p, 4) for p in mu_0])79
80    mu_1 = propagate_distribution(mu_0, p_mat)81    print("Step 1 distribution  (t=1):", [round(p, 4) for p in mu_1])82
83    mu_2 = propagate_distribution(mu_1, p_mat)84    print("Step 2 distribution  (t=2):", [round(p, 4) for p in mu_2])85
86    # 2. Monte Carlo environment sampling: draw 10,000 transitions from SafeRoad87    rng = random.Random(42)88    sample_counts = {s: 0 for s in states}89    trials = 1000090
91    for _ in range(trials):92        s_prime = env.sample_next_state("SafeRoad", "Forward", rng)93        sample_counts[s_prime] += 194
95    empirical_dist = {s: round(count / trials, 4) for s, count in sample_counts.items()}96    print("\nEmpirical frequencies after 10,000 trials from SafeRoad:")97    print(empirical_dist)98
99    # 3. Bellman expectation evaluation: E[V(S_{t+1}) | S_t = SafeRoad, A_t = Forward]100    state_values = {"SafeRoad": 2.0, "IcyPatch": 5.0, "Goal": 10.0}101    reward = -1.0102    gamma = 0.90103
104    expected_next_v = sum(105        prob * state_values[s_next]106        for s_next, prob in transitions[("SafeRoad", "Forward")].items()107    )108    q_value = reward + gamma * expected_next_v109
110    print(f"\nExpected successor value E[V(S')]: {expected_next_v:.2f}")111    print(f"Action value Q(SafeRoad, Forward):  {q_value:.2f}")112
113    # Explicit test assertions114    assert round(mu_1[1], 2) == 0.70, "Step 1 IcyPatch probability must equal 0.70"115    assert round(mu_2[2], 2) == 0.57, "Step 2 Goal probability must equal 0.57"116    assert round(q_value, 2) == 4.13, "Q-value must equal 4.13"

1Initial distribution (t=0): [1.0, 0.0, 0.0]2Step 1 distribution  (t=1): [0.1, 0.7, 0.2]3Step 2 distribution  (t=2): [0.15, 0.28, 0.57]4
5Empirical frequencies after 10,000 trials from SafeRoad:6{'SafeRoad': 0.0986, 'IcyPatch': 0.7045, 'Goal': 0.1969}7
8Expected successor value E[V(S')]: 5.709Action value Q(SafeRoad, Forward):  4.13

Watch Out For

The Quick Version

• Transition dynamics $P(s' \mid s, a) = \Pr(S_{t+1} = s' \mid S_t = s, A_t = a)$ govern the environment's physics by assigning a probability distribution over all possible next states given the current state and chosen action.
• The Markov property guarantees that future transitions depend solely on the current state-action pair $(s, a)$, making the preceding trajectory history conditionally independent.
• Every valid transition matrix must be row-stochastic: all probabilities must be non-negative and every row must sum to exactly $1.0$ ($\sum_{s'} P(s' \mid s, a) = 1$).
• Transition dynamics weight future value estimates during Bellman updates; model-based RL plans directly with $P(s' \mid s, a)$, while model-free methods sample from it via experience.

What to Read Next

• Markov Decision Processes
• Bellman Equations
• Value Functions