Module 2. State, Value, and Bellman Equations

Classify each case using the most accurate label:

• A. the observation is already a sufficient Markov state;
• B. the observation is incomplete, so partial observability is the natural model.

1. Only a ball's position is visible, while velocity is hidden and the dynamics have inertia.

2. A chess position includes the side to move, castling rights, and the en-passant status.

3. Pure autoregressive generation exposes the prompt and complete prefix, and the transition only appends the selected token.

4. An agent sees only the last two messages. An earlier tool message identified the open file, but it has been dropped from context; the next response depends on that file.

Write 1-?, 2-?, 3-?, 4-?. Then explain why “state is a compressed history” is a useful construction but not a universal definition of the environment state.

Choose three correct statements about a finite Markov decision process (MDP).

1. The policy $\pi(a\mid s)$ is part of $P(s'\mid s,a)$ and cannot change without changing the MDP.

2. The mean $\bar r(s,a)$ is obtained by averaging $\bar r(s,a,s')$ over next states with probabilities $P(s'\mid s,a)$; no conditional independence is needed.

3. The Markov property requires state to retain past information that matters for the next transition once the action is known.

4. A text transcript of tool use is automatically a complete state.

5. The same MDP can be paired with different policies.

6. A reward received on entry to a terminal state must be discarded because the terminal value is zero.

For each transition, choose the correct one-step TD target. Let $r=1$, $\gamma=0.9$, and $V(s')=4$.

1. The task reaches its terminal goal.

2. Data collection stops at an external limit although the process could continue.

3. The task is defined as “finish within 100 steps”; remaining budget is part of state and has been exhausted.

Options:

• A. $y=r=1$;
• B. $y=r+\gamma V(s')=4.6$.

Write 1-?, 2-?, 3-?, and explain why a single legacy done flag is insufficient.

Choose three correct statements that follow from the definitions without changing the MDP.

1. $V^\pi(s)$ always equals $\max_aQ^\pi(s,a)$.

2. $V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a)$.

3. $A^\pi(s,a)>0$ means the action is better than the current policy's average action in that state.

4. Arbitrary reward changes leave $A^\pi$ unchanged.

5. $\sum_aA^\pi(s,a)=0$ for every policy.

6. Adding a common constant $c(s)$ to every $Q(s,a)$ in one state, then recomputing $V$, leaves its advantages unchanged.

Select all applicable statements.

Choose five correct statements.

1. The Bellman expectation equation for a fixed policy is linear in $V^\pi$.

2. The optimality operator replaces policy averaging over actions with a maximum.

3. A Bellman equation is itself a complete neural-network training algorithm.

4. For $0\le\gamma<1$, $T_\pi$ and $T_*$ are $\gamma$-contractions in the max norm.

5. At $\gamma=1$, some proper episodic problems remain solvable, but the usual strict-contraction proof no longer applies.

6. A small Bellman residual always implies an equally small value error, independently of $\gamma$.

7. The fixed point of $T_\pi$ is the value of the fixed policy.

Match each method to its target.

Write A-?, B-?, C-?.

Then choose the most accurate statement:

1. MC always has lower variance than TD.

2. TD is always more accurate at every data budget.

3. The trade-off depends on the environment, horizon, representation, step size, and data budget.

4. Bootstrapping means resampling episodes with replacement.

Actions are collected by an $\varepsilon$-greedy policy. Choose the single most accurate statement.

1. SARSA and Q-learning are both off-policy because exploratory actions are random.

2. SARSA uses the actually selected $A_{t+1}$, whereas Q-learning uses $\max_{a'}Q(S_{t+1},a')$; Q-learning therefore evaluates a greedy target policy from $\varepsilon$-greedy behavior data.

3. Q-learning becomes off-policy only when a replay buffer is added.

4. SARSA cannot use $\varepsilon$-greedy exploration.

Choose four correct statements.

1. The group mean reward in canonical GRPO is an exact token-level $V^\pi(s_t)$ for every prefix.

2. Group normalization creates a relative signal without a learned critic, while remaining a sample statistic over complete responses.

3. The maximum of noisy unbiased estimates can exhibit positive selection bias.

4. Double Q-learning separates action selection from evaluation across two estimators.

5. Double Q-learning is exactly unbiased under every error dependence structure.

6. Selecting the highest-scoring LLM response under a noisy reward model shares a statistical mechanism with maximization bias, but is not literally tabular Q-learning.

At state $s$,

and

Compute $V^\pi(s)$ and both advantages. Verify the policy-weighted zero-mean identity.

State $s$ has two actions.

• $a_1$ deterministically reaches $s_1$ with reward $1$, where $V(s_1)=3$.
• $a_2$ reaches $s_2$ with probability $0.5$, reward $0$, and $V(s_2)=6$; or reaches $s_3$ with probability $0.5$, reward $2$, and $V(s_3)=1$.

Let $\gamma=0.9$. Compute both one-step action values, $(T_*V)(s)$, and the greedy action.

There is one non-terminal state $s$ and one terminal state. Under a fixed policy, state $s$

• moves to the terminal with probability $0.5$ and reward $0$;
• returns to $s$ with probability $0.5$ and reward $1$.

With $\gamma=0.9$, write and solve the Bellman equation for $V^\pi(s)$.

Let

Compute the new $V(s)$ for

1. an ordinary non-terminal transition;

2. a true terminal transition;

3. an external truncation while the process could continue.

Observed rewards are $[1,2,3]$, $\gamma=0.5$, and $V(S_{t+3})=4$. Compute

What changes if the third transition truly terminates the task?

At the next state,

Let $r=0.5$ and $\gamma=0.9$.

1. Compute a standard Q-learning target using $Q^A$ for both selection and evaluation.

2. Compute a Double-Q target that selects with $Q^A$ and evaluates with $Q^B$.

3. Explain the difference.

Implement two functions over arrays of shape (n_states, n_actions).

import numpy as np


def v_from_q(q_values: np.ndarray, policy: np.ndarray) -> np.ndarray:
    """V(s) = sum_a policy[s,a] * q_values[s,a]."""
    raise NotImplementedError


def advantage(q_values: np.ndarray, policy: np.ndarray) -> np.ndarray:
    """A(s,a) = Q(s,a) - V(s)."""
    raise NotImplementedError

Use the public checks below to verify shapes and the policy-weighted zero mean; the reference module provides further examples.

Open checks:

Q = np.array([[1.0, 3.0], [0.0, 2.0]])
pi = np.array([[0.5, 0.5], [0.2, 0.8]])
np.testing.assert_allclose(v_from_q(Q, pi), [2.0, 1.6])
np.testing.assert_allclose(advantage(Q, pi), [[-1.0, 1.0], [-1.6, 0.4]])
np.testing.assert_allclose((pi * advantage(Q, pi)).sum(axis=1), 0.0, atol=1e-12)

Solve the Bellman linear system over non-terminal states.

def exact_policy_value(
    transitions: np.ndarray,
    rewards: np.ndarray,
    policy: np.ndarray,
    gamma: float,
    terminals: np.ndarray,
) -> np.ndarray:
    """Return zero for terminal-state values."""
    raise NotImplementedError

Construct $P_\pi$ and $r_\pi$, then solve $(I-\gamma P_{NN})V_N=r_N$ on the non-terminal index set $N$.

Open check:

P = np.zeros((2, 1, 2))
R = np.zeros_like(P)
P[0, 0] = [0.5, 0.5]
R[0, 0] = [1.0, 0.0]
P[1, 0, 1] = 1.0
pi = np.ones((2, 1))
terminal = np.array([False, True])
np.testing.assert_allclose(
    exact_policy_value(P, R, pi, 0.9, terminal),
    [10.0 / 11.0, 0.0],
)

Implement one synchronous value-iteration backup.

def bellman_optimality_sweep(
    transitions: np.ndarray,
    rewards: np.ndarray,
    values: np.ndarray,
    gamma: float,
    terminals: np.ndarray,
) -> np.ndarray:
    """Return T_* V with zero terminal components."""
    raise NotImplementedError

Every new state value must be computed from the same old vector values.

Open check for one synchronous sweep:

P = np.zeros((3, 2, 3))
R = np.zeros_like(P)
P[0, 0, 1] = 1.0
P[0, 1, 2] = 1.0
R[0, 0, 1] = 1.0
R[0, 1, 2] = 2.0
P[1, :, 1] = 1.0
P[2, :, 2] = 1.0
V = np.array([0.0, 3.0, 1.0])
out = bellman_optimality_sweep(P, R, V, 0.9, np.zeros(3, dtype=bool))
assert abs(out[0] - 3.7) < 1e-12

Implement one-step and $n$-step targets. An external truncated=True flag must not mask the continuation by itself.

def td_target(reward, next_value, gamma, *, terminated, truncated=False):
    raise NotImplementedError


def n_step_target(rewards, bootstrap_value, gamma, *, terminated_at_end):
    raise NotImplementedError

The numerical checks are $2.8$, $1.0$, $2.8$ for ordinary/terminal/truncated one-step transitions and $3.25$, $2.75$ for the two three-step cases in Task B5.

Open checks:

assert td_target(1, 2, 0.9, terminated=False) == 2.8
assert td_target(1, 2, 0.9, terminated=True) == 1.0
assert td_target(1, 2, 0.9, terminated=False, truncated=True) == 2.8
assert abs(n_step_target([1, 2, 3], 4, 0.5, terminated_at_end=False) - 3.25) < 1e-12
assert abs(n_step_target([1, 2, 3], 4, 0.5, terminated_at_end=True) - 2.75) < 1e-12

Implement the local targets for a known next-state action-value vector.

def q_learning_target(reward, next_q_values, gamma, *, terminated):
    raise NotImplementedError


def sarsa_target(reward, next_q_values, next_action, gamma, *, terminated):
    raise NotImplementedError

Q-learning uses a maximum; SARSA uses the action actually selected by the behavior policy. Neither should bootstrap at a true terminal.

Open checks:

q_next = np.array([1.0, 4.0, 3.0])
assert q_learning_target(0.5, q_next, 0.9, terminated=False) == 4.1
assert sarsa_target(0.5, q_next, 2, 0.9, terminated=False) == 3.2
assert q_learning_target(1.0, np.array([]), 0.9, terminated=True) == 1.0
assert sarsa_target(1.0, np.array([]), 99, 0.9, terminated=True) == 1.0

Implement a Double-Q target. One estimator selects the action index; the other evaluates that selected index.

def double_q_target(
    reward: float,
    selector_q: np.ndarray,
    evaluator_q: np.ndarray,
    gamma: float,
    *,
    terminated: bool,
) -> float:
    raise NotImplementedError

For selector=[1,4,3], evaluator=[10,2,8], $r=0.5$, and $\gamma=0.9$, the non-terminal result must be $2.3$.

Open checks:

qa = np.array([1.0, 4.0, 3.0])
qb = np.array([10.0, 2.0, 8.0])
assert double_q_target(0.5, qa, qb, 0.9, terminated=False) == 2.3
assert double_q_target(0.5, qa, qb, 0.9, terminated=True) == 0.5