Reinforcement Learning Basics

Predicting a review label answers one question about a request. Choosing what to do next raises another: how will this action change the evidence, delay, and outcome? At 09:00, access-change request REQ-10234 lands on the routing desk under fictional policy P-7. The router could approve immediately, request supporting evidence, or escalate to a human reviewer. Compare the futures those choices create.

The earlier tree-model lesson fitted completed-case labels from static snapshots; supervised labels can arrive much later than predictions. Here, requesting evidence changes the next observation. Reinforcement learning (RL) learns decisions from rewards and their consequences.^{[1]Reference 1Reinforcement Learning: An Introductionhttp://incompleteideas.net/book/the-book-2nd.html} Experience can come from interaction, simulation, or historical logs. The agent chooses routing actions; the environment includes the requester, verification service, and reviewers. We optimize expected cumulative return under a declared reward and discount, rather than only the next reward.

Teaching scores below are synthetic reward units, not dollar amounts or live production parameters. The unsafe approval option stays in our simulator to expose failure patterns. Real authorization layers must enforce hard invariants through deterministic guardrails rather than relying on a learned penalty to prevent policy violations.

From one label to an episode

REQ-10234 is a stale access-change request. Security policy P-7 requires human review unless strong secondary evidence arrives. Three opening actions are available:

Before checking the mathematical totals, pause and predict: if evidence definitely arrives, does the fastest action win, or can a small upfront delay pay for a higher-value outcome?

An episode starts at new_request and terminates at closed. Suppose evidence arrives with absolute certainty, giving these reward sequences:

Without discounting, evidence earns $-4 + 70 = 66$ while human review earns $-18 + 80 = 62$. Now discount rewards observed one step later by a factor of $\gamma = 0.90$. The evidence route earns $-4 + 0.90 \times 70 = 59.0$. Human review earns $-18 + 0.90 \times 80 = 54.0$. Immediate approval still incurs $-120.0$. The evidence route leads by five points when evidence arrives reliably.

The discounted return $G_t$ accumulates rewards across time steps with increasing powers of $\gamma$:

Here $R_{t+1}$ is received after action $A_t$ from state $S_t$. The discount factor is $\gamma=0.90$ in our model.^{[1]Reference 1Reinforcement Learning: An Introductionhttp://incompleteideas.net/book/the-book-2nd.html} Two roles need distinguishing:

1. A bounded continuing return: With $0\le\gamma<1$ and $|R_t|\le R_{\max}$, $|G_t|\le R_{\max}/(1-\gamma)$. Undiscounted continuing sums may diverge; average-reward formulations are another legitimate objective.
2. A chosen temporal preference: Discounting downweights later positive rewards and later penalties. It can favor earlier resolution, but can also make a delayed violation look cheaper. Uncertain dynamics need their own model or robustness analysis.

Every branch here terminates within three transitions, so $\gamma=1$ would also give finite returns. Each transition represents an operational step, not necessarily an equal duration: a constant per-step discount doesn't price hours consistently if step lengths differ. We model abandonment explicitly below. A discount has an equivalent survival interpretation only under suitable independent termination with zero reward on termination; it can't replace our action-dependent abandonment penalty.

The Python script applies those weights directly to each path:

gamma = 0.90
routes = {
    "auto_approve": [-120],
    "request_evidence": [-4, 70],
    "human_review": [-18, 80],
}

def discounted_return(rewards):
    return sum((gamma**step) * reward for step, reward in enumerate(rewards))

assert discounted_return([-4, 70]) == 59.0
assert discounted_return([-18, 80]) == 54.0
for action, rewards in routes.items():
    print(f"{action:16} return={discounted_return(rewards):7.1f}")

auto_approve     return= -120.0
request_evidence return=   59.0
human_review     return=   54.0

That five-point advantage relies on evidence arriving every time. If the next observation depends on the action just taken, which facts does the router have to remember?

Define the MDP

The router has to remember whether verified evidence has arrived, because that fact changes both the next state and the reward of auto_approve. A Markov decision process (MDP) keeps that memory in a 5-tuple $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma)$:

• States $\mathcal{S}$: The set of all valid environment configurations. $S_t \in \mathcal{S}$ captures what's known at decision time $t$.
• Actions $\mathcal{A}(s)$: The set of choices available in state $s$.
• Transition dynamics $\mathcal{P}$: The conditional probability distribution $\mathcal{P}(s' \mid s, a) = \mathbb{P}(S_{t+1} = s' \mid S_t = s, A_t = a)$.
• Reward function $\mathcal{R}$: The expected immediate reward $\mathcal{R}(s, a, s') = \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s']$.
• Discount factor $\gamma \in [0, 1)$: The decay rate for future rewards.

Sequential interaction between the agent and environment repeats until termination:

View larger

Under the Markov assumption, the current state and action contain all information needed to predict the next state and reward distribution:

The past adds nothing to this distribution once the state and action are known.^{[1]Reference 1Reinforcement Learning: An Introductionhttp://incompleteideas.net/book/the-book-2nd.html} If elapsed wait affects abandonment, omitting it can make our chosen representation non-Markov. An MDP environment may expose only partial observations to the agent; model that as a POMDP or use a sufficient history or belief representation. Dropping a field doesn't itself change the underlying environment.

Begin with a deterministic environment where transitions occur with probability $1.0$:

Evidence changes whether auto_approve is permitted under policy P-7, so new_request and evidence_ready must be distinct states.

The graph uses shortened action labels: evidence means request_evidence, review means human_review, and auto means auto_approve. Each edge carries its immediate reward.

View larger

The graph shows where each action lands and what it pays immediately. It doesn't yet say which state is worth being in once later rewards are discounted.

Value and Bellman backups

A state's worth depends on which action comes next. A policy $\pi$ defines how the agent behaves. A deterministic policy maps each state directly to a single action: $a = \pi(s)$. A stochastic policy outputs an action distribution: $\pi(a \mid s) = \mathbb{P}(A_t = a \mid S_t = s)$.

Two foundational value functions measure performance under a policy $\pi$:

• State-value function $V^\pi(s)$: The expected return starting from state $s$ and following policy $\pi$ thereafter: $$V^\pi(s) = \mathbb{E}_\pi [G_t \mid S_t = s]$$
• Action-value function $Q^\pi(s, a)$: The expected return starting from state $s$, taking action $a$, and following policy $\pi$ thereafter: $$Q^\pi(s, a) = \mathbb{E}_\pi [G_t \mid S_t = s, A_t = a]$$

The connection between state values and action values is defined by the Bellman expectation equations. We decompose the return into immediate reward plus the discounted value of the successor state:

When seeking optimal control, we aren't satisfied with an arbitrary policy. The optimal policy $\pi^*$ achieves the highest possible return across all states: $V^*(s) = \max_\pi V^\pi(s)$ for all $s \in \mathcal{S}$. This produces the Bellman optimality equations:

The backward calculation updating a state's value from its successors is called a Bellman backup. Starting from terminal outcomes and walking backward:

• Terminal state closed has no future transitions: $V^*(\texttt{closed}) = 0$.
• review_queue has one action (approve_request): $V^*(\texttt{review\_queue}) = 80 + 0.90 \times 0 = 80.0$.
• evidence_ready compares auto-approval against human review: $$Q^*(\texttt{evidence\_ready}, \texttt{auto\_approve}) = 70 + 0.90 \times 0 = 70.0$$ $$Q^*(\texttt{evidence\_ready}, \texttt{human\_review}) = -10 + 0.90 \times 80 = 62.0$$ $$V^*(\texttt{evidence\_ready}) = \max(70.0, 62.0) = 70.0$$
• new_request compares all three opening options: $$Q^*(\texttt{new\_request}, \texttt{auto\_approve}) = -120 + 0.90 \times 0 = -120.0$$ $$Q^*(\texttt{new\_request}, \texttt{request\_evidence}) = -4 + 0.90 \times 70 = 59.0$$ $$Q^*(\texttt{new\_request}, \texttt{human\_review}) = -18 + 0.90 \times 80 = 54.0$$ $$V^*(\texttt{new\_request}) = \max(-120.0, 59.0, 54.0) = 59.0$$

The backup tree shows how action values feed into the root state:

View larger

The script performs this exact comparison and extracts the greedy action:

gamma = 0.90
successor_value = {
    "closed": 0.0,
    "evidence_ready": 70.0,
    "review_queue": 80.0,
}
start_actions = {
    "auto_approve": (-120, "closed"),
    "request_evidence": (-4, "evidence_ready"),
    "human_review": (-18, "review_queue"),
}

scores = {
    action: reward + gamma * successor_value[next_state]
    for action, (reward, next_state) in start_actions.items()
}
assert scores["request_evidence"] == 59.0
assert scores["human_review"] == 54.0
for action, score in scores.items():
    print(f"Q(new_request, {action:16}) = {score:7.1f}")
print("greedy action =", max(scores, key=scores.get))

Q(new_request, auto_approve    ) =  -120.0
Q(new_request, request_evidence) =    59.0
Q(new_request, human_review    ) =    54.0
greedy action = request_evidence

One backup was enough because this graph is tiny, every path ends, and the successor values were already known. What fills those values in when you can't write every backup by hand?

Dynamic programming: value iteration vs policy iteration

Repeated Bellman backups fill them in, once the transitions and expected rewards are known. For a finite discounted MDP, that sweep is dynamic programming, and it can compute an optimal policy. Two standard algorithms are:

• Policy Iteration: Operates in two distinct alternating phases:
  1. Policy Evaluation: Solve the Bellman expectation equations for a fixed policy $\pi_k$, using a linear solve or iterative evaluation. Practical iterations use a tolerance.
  2. Policy Improvement: Extract a strictly better or equal policy greedily: $\pi_{k+1}(s) = \arg\max_a Q^{\pi_k}(s, a)$. Exact evaluation and greedy improvement give $V^{\pi_{k+1}}\ge V^{\pi_k}$. There are finitely many deterministic policies, $\prod_s|\mathcal A(s)|$; stochastic policies aren't a finite set. With consistent tie handling, exact policy iteration terminates at an optimum. Approximate evaluation needs its own error control rather than an automatic exact guarantee.
• Value Iteration: Avoids waiting for complete policy evaluation. Instead, it collapses evaluation and improvement into a single step by directly applying the Bellman optimality operator on every sweep: $$V_{k+1}(s) \leftarrow \max_{a \in \mathcal{A}(s)} \sum_{s'} \mathcal{P}(s' \mid s, a) \left[ \mathcal{R}(s, a, s') + \gamma V_k(s') \right]$$

For this finite model with bounded rewards and $\gamma<1$, the Bellman optimality operator contracts under the infinity norm: $\|T^*u-T^*v\|_\infty\le\gamma\|u-v\|_\infty$. Exact repeated backups converge geometrically to a unique $V^*$ from any finite initialization. Optimal actions can still tie, so uniqueness of the value doesn't imply a unique optimal policy.

Watch how credit propagates backward across three sweeps:

gamma = 0.90
states = ["new_request", "evidence_ready", "review_queue", "closed"]
actions = {
    "new_request": ["auto_approve", "request_evidence", "human_review"],
    "evidence_ready": ["auto_approve", "human_review"],
    "review_queue": ["approve_request"],
}
transitions = {
    ("new_request", "auto_approve"): [(1.0, "closed", -120)],
    ("new_request", "request_evidence"): [(1.0, "evidence_ready", -4)],
    ("new_request", "human_review"): [(1.0, "review_queue", -18)],
    ("evidence_ready", "auto_approve"): [(1.0, "closed", 70)],
    ("evidence_ready", "human_review"): [(1.0, "review_queue", -10)],
    ("review_queue", "approve_request"): [(1.0, "closed", 80)],
}

def action_value(state, action, values):
    return sum(
        probability * (reward + gamma * values[next_state])
        for probability, next_state, reward in transitions[(state, action)]
    )

values = {state: 0.0 for state in states}
for sweep in range(3):
    updated = values.copy()
    for state in actions:
        updated[state] = max(
            action_value(state, action, values) for action in actions[state]
        )
    values = updated
    print(
        f"sweep {sweep + 1}: "
        f"new={values['new_request']:5.1f} "
        f"evidence={values['evidence_ready']:5.1f} "
        f"review={values['review_queue']:5.1f}"
    )

policy = {
    state: max(actions[state], key=lambda action: action_value(state, action, values))
    for state in actions
}
assert values["new_request"] == 59.0
assert policy["new_request"] == "request_evidence"
print("policy =", policy)

sweep 1: new= -4.0 evidence= 70.0 review= 80.0
sweep 2: new= 59.0 evidence= 70.0 review= 80.0
sweep 3: new= 59.0 evidence= 70.0 review= 80.0
policy = {'new_request': 'request_evidence', 'evidence_ready': 'auto_approve', 'review_queue': 'approve_request'}

On sweep 1, all successor estimates start at zero, so new_request sees only immediate costs ($\max(-120, -4, -18) = -4$). On sweep 2, the newly calculated values of evidence_ready ($70.0$) and review_queue ($80.0$) propagate backward, lifting new_request to $59.0$. On sweep 3, values stabilize completely.

Value iteration solves planning when dynamics are known. What happens when our assumption of certain evidence arrival breaks down?

Transition risk can reverse a decision

Real users don't always cooperate. When asked for additional authentication credentials, some users close the tab and abandon the flow. Add an abandonment branch: with probability $p = 0.25$, the requester walks away. The ticket closes unresolved, incurring a $-50$ penalty alongside the initial $-4$ dispatch cost, totaling $-54$:

Under this model, the expected counts in 100 independent requests are 75 arrivals and 25 abandonments; realized counts vary. We charge abandonment on the opening transition. If it occurred after a separate waiting step, its timing and discounted return would need changing. Weight the current branches by their probabilities:

Direct human review remains deterministic: $-18 + 0.90 \times 80 = 54.0$. Comparing the two choices under risk:

The expected Bellman backup flips the optimal action from request_evidence to human_review!

We can solve for the exact indifference threshold. Let $p$ be the abandonment probability. The expected return for requesting evidence as a function of $p$ is:

Equating this expected return to human review's constant value of $54$:

Above $4.42\%$ abandonment, human review has higher expected return under these rewards and timings. This isn't a universal product threshold.

The stochastic backup script reflects this calculation:

gamma = 0.90
values = {"closed": 0.0, "evidence_ready": 70.0, "review_queue": 80.0}
transitions = {
    "request_evidence": [
        (0.75, "evidence_ready", -4),
        (0.25, "closed", -54),
    ],
    "human_review": [(1.0, "review_queue", -18)],
}

def expected_action_value(action):
    return sum(
        probability * (reward + gamma * values[next_state])
        for probability, next_state, reward in transitions[action]
    )

assert expected_action_value("request_evidence") == 30.75
assert expected_action_value("human_review") == 54.0
for action in transitions:
    print(f"{action:16} expected return={expected_action_value(action):5.2f}")
print("risk-aware action =", max(transitions, key=expected_action_value))

request_evidence expected return=30.75
human_review     expected return=54.00
risk-aware action = human_review

The $30.75$ expectation isn't a return any single ticket achieves. Check a sample mean from 10,000 simulated episodes against it. One seeded run can check the simulator's arithmetic without proving convergence or validating real abandonment rates:

import random

gamma = 0.90
rng = random.Random(7)

def request_evidence_return():
    if rng.random() < 0.75:
        return -4 + gamma * 70
    return -54

evidence_returns = [request_evidence_return() for _ in range(10_000)]
evidence_mean = sum(evidence_returns) / len(evidence_returns)
abandoned = sum(value < 0 for value in evidence_returns)
assert abs(evidence_mean - 30.75) < 1.0
print(f"request_evidence mean={evidence_mean:5.2f}")
print(f"human_review     mean={-18 + gamma * 80:5.2f}")
print("abandoned evidence routes =", abandoned)

request_evidence mean=30.73
human_review     mean=54.00
abandoned evidence routes = 2502

Unknown dynamics leave two choices: estimate a model and plan with it, or learn values or policies directly from sampled transitions. Model-free learning takes the latter route; unknown probabilities don't force it.

Model-free learning: temporal difference updates

Our model-free learner receives sampled experience tuples $(S_t,A_t,R_{t+1},S_{t+1})$ rather than a transition table.

Two primary approaches address this challenge:

• Monte Carlo (MC) methods: Update value estimates using the actual realized total return $G_t$ observed at the end of the episode: $$V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)]$$
  • Target: For a fixed policy and correctly sampled completed episodes, $G_t$ has conditional expectation $V^\pi(S_t)$. That doesn't make an arbitrarily initialized, finite-data value estimate unbiased.
  • Noise: The target includes all later randomness; long stochastic episodes can produce high variance, while deterministic returns can have none.
  • Timing: Standard episodic MC waits for the completed return. A truncated discounted rollout can approximate a continuing return, but introduces tail error; appending a value estimate makes a bootstrapped target.
• Temporal Difference (TD) learning: Bootstraps future return using the agent's current estimate at the next state $V(S_{t+1})$: $$V(S_t) \leftarrow V(S_t) + \alpha \delta_t$$ where the TD error $\delta_t$ is defined as: $$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$$ The target $R_{t+1} + \gamma V(S_{t+1})$ replaces the unobserved tail of the episode.
  • Target: Bootstrapping from an inaccurate successor value can introduce target bias. With exact $V^\pi$, the one-step target has conditional expectation $V^\pi(S_t)$.
  • Noise: Replacing a sampled tail with its exact conditional expectation reduces target variance. A learned approximation adds its own errors, so TD doesn't have universally lower finite-data variance or error than MC.
  • Benefit: Updates immediately on every time step without waiting for episode termination.

For control tasks where we must select actions without a model, we learn action values $Q(s, a)$ rather than state values $V(s)$. Two algorithms frame the core design choice:

• Q-Learning (Watkins, 1989 ^{[2]Reference 2Q-learninghttps://doi.org/10.1007/BF00992698}): An off-policy TD control algorithm. It updates $Q(S_t, A_t)$ toward the greedy maximum in the next state: $$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t) \right]$$ Because the target uses $\max_{a'} Q(S_{t+1}, a')$, Q-learning targets the optimal action-value function $Q^*$ even while the agent follows an exploratory behavior policy (such as $\varepsilon$-greedy). A greedy action choice from those values defines the target policy.
• SARSA (Sutton & Barto ^{[1]Reference 1Reinforcement Learning: An Introductionhttp://incompleteideas.net/book/the-book-2nd.html}): An on-policy TD control algorithm. It uses the transition $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$: $$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right]$$ Here $A_{t+1}$ is the action actually selected by the current behavior policy. SARSA learns the value of the policy being executed, incorporating the cost of exploratory mistakes.

For a stationary finite MDP with bounded rewards and $\gamma<1$, tabular Q-learning converges to $Q^*$ almost surely when every state-action pair is updated infinitely often and its own visit-indexed step sizes satisfy $\sum_n\alpha_n(s,a)=\infty$ and $\sum_n\alpha_n(s,a)^2<\infty$.^{[2]Reference 2Q-learninghttps://doi.org/10.1007/BF00992698[1]Reference 1Reinforcement Learning: An Introductionhttp://incompleteideas.net/book/the-book-2nd.html} This theorem describes asymptotic behavior under those conditions. A finite run provides a sample trajectory; neural Q-functions require separate convergence analysis.

To ensure exploration, we apply epsilon-greedy exploration: with probability $\varepsilon$, choose an action uniformly at random; with probability $1 - \varepsilon$, select the highest-scoring action.

The simulator's step function below contains the transition dynamics and rewards; the learner receives only sampled outcomes:

import random

gamma = 0.90
epsilon = 0.15
rng = random.Random(42)
actions = {
    "new_request": ["auto_approve", "request_evidence", "human_review"],
    "evidence_ready": ["auto_approve", "human_review"],
    "review_queue": ["approve_request"],
}

def step(state, action):
    if state not in actions or action not in actions[state]:
        raise ValueError("invalid state-action pair")
    if state == "new_request":
        if action == "auto_approve":
            return "closed", -120
        if action == "human_review":
            return "review_queue", -18
        if rng.random() < 0.75:
            return "evidence_ready", -4
        return "closed", -54
    if state == "evidence_ready":
        return ("closed", 70) if action == "auto_approve" else ("review_queue", -10)
    return "closed", 80

q = {
    state: {action: 0.0 for action in available_actions}
    for state, available_actions in actions.items()
}
visits = {
    state: {action: 0 for action in available_actions}
    for state, available_actions in actions.items()
}
for _ in range(20_000):
    state = "new_request"
    while state != "closed":
        available_actions = actions[state]
        if rng.random() < epsilon:
            action = rng.choice(available_actions)
        else:
            action = max(available_actions, key=lambda candidate: q[state][candidate])
        next_state, reward = step(state, action)
        future = 0.0 if next_state == "closed" else max(q[next_state].values())
        target = reward + gamma * future
        visits[state][action] += 1
        learning_rate = visits[state][action] ** -0.6
        q[state][action] += learning_rate * (target - q[state][action])
        state = next_state

start = q["new_request"]
assert max(start, key=start.get) == "human_review"
assert 20.0 < start["request_evidence"] < 40.0
for action, value in start.items():
    print(f"Q(new_request, {action:16}) = {value:6.1f}")
print("learned start action =", max(start, key=start.get))

Q(new_request, auto_approve    ) = -120.0
Q(new_request, request_evidence) =   30.5
Q(new_request, human_review    ) =   54.0
learned start action = human_review

After this seeded run, request_evidence is estimated near $30.5$, close to the analytic $30.75$. The convergence theorem is asymptotic and assumes conditions such as step-size sums and repeated visits. Our visit-indexed rate $n^{-0.6}$ satisfies the two step-size sums; constant exploration supplies repeated visits in this reachable toy graph, while the seeded run reports one finite trajectory. The greedy extracted policy chooses review, but the training behavior still explores. Once review is the unique greedy opening action, it is selected with probability 0.85 + 0.15/3 = 0.90; each other action still receives probability 0.05. Random exploration can also select the greedy action, so its probability isn't just 1 - epsilon. The simulator accepts only declared state-action pairs; its unsafe opening action remains solely for this experiment.

A stopped rollout isn't always a terminal request

The lab sets future value to zero when the ticket reaches closed. An external collection time limit is different: the ticket may still have a valuable future. Gymnasium distinguishes terminated from truncated; a one-step bootstrap masks genuine termination, not merely truncation.^{[3]Reference 3Handling Time Limitshttps://gymnasium.farama.org/tutorials/gymnasium_basics/handling_time_limits/}

reward, gamma, next_value = -18.0, 0.90, 80.0

for label, terminated, truncated in (
    ("external time limit", False, True),
    ("terminal outcome", True, False),
):
    stopped = terminated or truncated
    correct = reward + gamma * (not terminated) * next_value
    erased_tail = reward + gamma * (not stopped) * next_value
    print(f"{label}: target={correct:.1f}; stop-masked target={erased_tail:.1f}")

external time limit: target=54.0; stop-masked target=-18.0
terminal outcome: target=-18.0; stop-masked target=-18.0

The same observed reward produces different targets because the future differs. A deadline built into the task can be a genuine terminal condition. Include remaining time in the state when it affects decisions. Use the actual final observation for a truncated bootstrap, rather than a reset observation from an automatically reset environment.

Those updates only revise actions the learner actually tries. What happens to an action that stays at its starting zero?

Exploration and action coverage

With zero initialization, deterministic tie handling, and no exploration, a positive learned action value can keep an untried zero-valued action from being selected. A stochastic return or optimistic initialization could change that behavior. Replace each whole path with its true expected value and watch human_review receive zero visits:

import random

true_returns = {
    "auto_approve": -120.0,
    "request_evidence": 30.75,
    "human_review": 54.0,
}
action_order = list(true_returns)

def learn(epsilon, seed):
    rng = random.Random(seed)
    estimates = {action: 0.0 for action in action_order}
    visits = {action: 0 for action in action_order}
    for _ in range(400):
        if rng.random() < epsilon:
            action = rng.choice(action_order)
        else:
            action = max(action_order, key=lambda candidate: estimates[candidate])
        visits[action] += 1
        estimates[action] += (true_returns[action] - estimates[action]) / visits[action]
    selected = max(action_order, key=lambda candidate: estimates[candidate])
    return visits, selected

greedy_visits, greedy_selected = learn(0.00, seed=5)
explore_visits, explore_selected = learn(0.10, seed=1)
assert greedy_selected == "request_evidence"
assert greedy_visits["human_review"] == 0
assert explore_selected == "human_review"
for epsilon, visits, selected in (
    (0.00, greedy_visits, greedy_selected),
    (0.10, explore_visits, explore_selected),
):
    print(f"epsilon={epsilon:.2f} visits={visits} selected={selected}")

epsilon=0.00 visits={'auto_approve': 1, 'request_evidence': 399, 'human_review': 0} selected=request_evidence
epsilon=0.10 visits={'auto_approve': 17, 'request_evidence': 28, 'human_review': 355} selected=human_review

With $\varepsilon = 0$, human_review receives zero visits. The agent remains blind to the superior $54.0$ return and commits forever to request_evidence. With $\varepsilon = 0.10$, exploration samples all actions, discovers review's higher value, and concentrates $355$ out of $400$ decisions on the true optimum.

In production access systems, you can't freely explore dangerous actions on live traffic. Instead, restrict the action space through policy guardrails prior to model evaluation, or conduct exploration inside high-fidelity staging environments.

Reward specification is part of the system

Reinforcement learning agents optimize the numeric signal they receive, not the unspoken intent in an engineering spec. When rewards measure only convenient proxies, agents find unexpected loopholes.

Consider what happens if an optimization team rewards fast ticket closure:

actions = ["auto_approve", "request_evidence", "human_review"]
speed_only = {
    "auto_approve": 100,
    "request_evidence": 45,
    "human_review": 15,
}
outcome_aware = {
    "auto_approve": -120,
    "request_evidence": 30.75,
    "human_review": 54.0,
}

for name, reward in [("speed_only", speed_only), ("outcome_aware", outcome_aware)]:
    choice = max(actions, key=lambda action: reward[action])
    print(f"{name:13} chooses {choice:16} reward={reward[choice]:4}")

speed_only    chooses auto_approve     reward= 100
outcome_aware chooses human_review     reward=54.0

The speed-only reward selects auto_approve. It maximizes the turnaround number by approving a request that policy P-7 forbids. That is Goodhart's Law in this table: once the proxy is the target, it stops tracking the outcome you meant. The compliance boundary belongs in the execution filter, not only in the reward.

Policy gradients and the LLM bridge

Tabular methods store a separate value for each state-action pair. A language-model state is a token prefix, and there are too many prefixes to store a table. A parameterized policy $\pi_\theta(a \mid s)$ lets the network weights $\theta$ output the action probabilities directly.

For an episode ending at $S_T$, define $J(\theta)=\mathbb E_{\tau\sim\pi_\theta}[G_0]$ from a fixed initial-state distribution. Assume differentiable policies and environment dynamics that don't depend directly on $\theta$. The trajectory score identity and reward-to-go argument give:^{[1]Reference 1Reinforcement Learning: An Introductionhttp://incompleteideas.net/book/the-book-2nd.html}

Sampling this expectation gives REINFORCE updates.^{[4]Reference 4Simple statistical gradient-following algorithms for connectionist reinforcement learninghttps://link.springer.com/article/10.1007/BF00992696} We don't need a transition table, but do need experience from the appropriate policy. The outer $\gamma^t$ measures time from the episode's start; $G_t$ discounts only from the current step. It disappears for an undiscounted episodic objective with $\gamma=1$.

Check that distinction with a two-step episode: the opening action is fixed, the second action is Bernoulli with probability $\sigma(\theta)$, and it earns reward 1 only when action 1 is selected. Thus $J(\theta)=\gamma\sigma(\theta)$. At $\theta=0$, which derivative should REINFORCE reproduce?

from math import exp

gamma, theta = 0.90, 0.0

def probability(parameter):
    return 1 / (1 + exp(-parameter))

p = probability(theta)
second_step_gradient = sum(
    action_probability * (action - p) * action
    for action, action_probability in ((0, 1 - p), (1, p))
)
weighted_gradient = gamma * second_step_gradient
delta = 1e-5
finite_difference = gamma * (
    probability(theta + delta) - probability(theta - delta)
) / (2 * delta)
assert abs(weighted_gradient - finite_difference) < 1e-9
print(f"with the time weight: {weighted_gradient:.4f}")
print(f"without the time weight: {second_step_gradient:.4f}")
print(f"objective finite difference: {finite_difference:.4f}")

with the time weight: 0.2250
without the time weight: 0.2500
objective finite difference: 0.2250

A baseline changes variance, not the intended gradient

Subtract an action-independent, state-dependent baseline $b(S_t)$, often an estimate of $V^\pi(S_t)$. The true advantage is:

The sampled quantity $G_t-b(S_t)$ estimates that advantage when $b=V^\pi$; it isn't the exact action value. Because $\mathbb E_{A_t\sim\pi_\theta}[\nabla_\theta\log\pi_\theta(A_t\mid S_t)b(S_t)]=0$, an action-independent baseline leaves the score estimator's expectation unchanged.^{[1]Reference 1Reinforcement Learning: An Introductionhttp://incompleteideas.net/book/the-book-2nd.html[5]Reference 5Part 3: Intro to Policy Optimizationhttps://spinningup.openai.com/en/latest/spinningup/rl_intro3.html} Treat it as a fixed weight when differentiating the actor loss. A baseline fitted using the same action's return needs care; action independence isn't automatic.

Variance reduction depends on the baseline. In a one-step Bernoulli policy with $p=0.5$ and reward equal to the selected action, compare no baseline, the exact value baseline, and a badly chosen baseline:

for baseline in (0.0, 0.5, 10.0):
    gradients = [(action - 0.5) * (action - baseline) for action in (0, 1)]
    mean_gradient = sum(gradients) / 2
    variance = sum((value - mean_gradient)**2 for value in gradients) / 2
    print(f"baseline={baseline:.1f}: mean={mean_gradient:.4f}; variance={variance:.4f}")

baseline=0.0: mean=0.2500; variance=0.0625
baseline=0.5: mean=0.2500; variance=0.0000
baseline=10.0: mean=0.2500; variance=22.5625

All three have the correct mean derivative, but one makes sampling much noisier. The exact value baseline removes variance in this tiny example; it isn't universally the variance-minimizing baseline for every parameterization.

Return to the router. Freeze all downstream choices at the model's optimal actions and optimize only the opening softmax policy. The script sums over its three known action values exactly and checks the derivative against finite differences. It computes an opening-policy gradient; a whole-policy REINFORCE trainer would sample trajectories and update all policy decisions:

import math

actions = ["auto_approve", "request_evidence", "human_review"]
action_values = [-120.0, 30.75, 54.0]
logits = [0.0, 0.0, 0.0]

def softmax(values):
    peak = max(values)
    weights = [math.exp(value - peak) for value in values]
    total = sum(weights)
    return [weight / total for weight in weights]

probabilities = softmax(logits)
baseline = sum(p * value for p, value in zip(probabilities, action_values))
advantages = [value - baseline for value in action_values]
n = len(actions)
gradient = [0.0] * n
for i, advantage in enumerate(advantages):
    for j in range(n):
        score = (1.0 if i == j else 0.0) - probabilities[j]
        gradient[j] += probabilities[i] * score * advantage

def objective(candidate_logits):
    return sum(p * value for p, value in zip(softmax(candidate_logits), action_values))

delta = 1e-5
for j in range(n):
    plus, minus = logits.copy(), logits.copy()
    plus[j] += delta
    minus[j] -= delta
    finite_difference = (objective(plus) - objective(minus)) / (2 * delta)
    assert abs(gradient[j] - finite_difference) < 1e-6

updated = softmax([logit + 0.03 * value for logit, value in zip(logits, gradient)])
assert abs(updated[0] - 0.089) < 0.001
assert abs(updated[2] - 0.508) < 0.001
for action, before, after in zip(actions, probabilities, updated):
    print(f"{action:16} before={before:.3f} after={after:.3f}")
print("exact gradient matches finite differences")

auto_approve     before=0.333 after=0.089
request_evidence before=0.333 after=0.403
human_review     before=0.333 after=0.508
exact gradient matches finite differences

The gradient step pushes the human review probability from $0.333$ to $0.508$, while driving the policy-violating auto-approval down to $0.089$.

For a text-only completion with no external tool interaction, token generation has a useful MDP representation:

• State $S_t$: The prompt plus $t$ generated tokens, $S_t=(x,y_1,\dots,y_t)$; $S_0$ is just the prompt.
• Action $A_t$: The next token $y_{t+1}\in\mathcal V$, including an end-of-sequence token. Vocabulary size depends on the model.
• Transition dynamics: Deterministic token appending: $S_{t+1} = (S_t, A_t)$.
• Reward $R$: Typically a sparse scalar assigned at sequence completion by a trained reward model $r_\phi(x, y)$ or an automated verifier (such as unit test execution or mathematical proof checks).

Tool-using agents also have external observations and actions; appending a token doesn't describe all their environment dynamics. Prompt difficulty, the reward's units, termination, and token-length weighting remain part of the training objective.

In classical RLHF (Ouyang et al., 2022 ^{[6]Reference 6Training Language Models to Follow Instructions with Human Feedback (InstructGPT).https://arxiv.org/abs/2203.02155}), Proximal Policy Optimization (PPO, Schulman et al., 2017 ^{[7]Reference 7Proximal Policy Optimization Algorithms.https://arxiv.org/abs/1707.06347}) optimizes the language model:

1. An actor network $\pi_\theta$ generates candidate completions.
2. A separate critic network $V_\psi(s)$ predicts expected reward from partial token sequences, providing token-level baselines for generalized advantage estimation (GAE).
3. A frozen reference model $\pi_{\text{ref}}$ penalizes large divergence from the initial supervised model using a token-level Kullback-Leibler (KL) penalty: $\mathbb{D}_{\text{KL}}(\pi_\theta \parallel \pi_{\text{ref}})$.

The human-preference reward model is a fourth role, scoring completions. Architectures can share weights across these roles or implement them with separate networks. A separate large critic adds weights, training state, compute, and communication; total memory depends on the chosen architecture.

PPO's clipped surrogate compares the current policy with the policy that sampled the rollout. That older sampling policy and the frozen reference serve different purposes. Clipping discourages some large probability-ratio changes; it doesn't impose a hard KL bound or guarantee improvement under repeated optimization.^{[7]Reference 7Proximal Policy Optimization Algorithms.https://arxiv.org/abs/1707.06347}

DeepSeek introduced Group Relative Policy Optimization (GRPO) in DeepSeekMath (2024) and used it in DeepSeek-R1 (2025). The original recipe provides a critic-free example, rather than a complete description of every current GRPO variant:^{[8]Reference 8DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelshttps://arxiv.org/abs/2402.03300[9]Reference 9DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learninghttps://arxiv.org/abs/2501.12948}

• Eliminating the critic: GRPO doesn't train a separate value network $V_\psi$.
• Group sampling: For each input prompt $q$, the policy samples a group of $G$ independent completions: $\{o_1, o_2, \dots, o_G\} \sim \pi_{\theta_{\text{old}}}(\cdot \mid q)$.
• Group-relative score: Each completion receives a reward $r_i$. DeepSeekMath describes learned outcome and process reward models; R1's reasoning RL uses rule-based accuracy and format rewards. For outcome supervision, normalize the completion scores across the group, with a small numerical stabilizer: $$A_i = \frac{r_i - \text{mean}(\{r_1, \dots, r_G\})}{\text{std}(\{r_1, \dots, r_G\}) + \epsilon}$$
• Objective: Use a PPO-style clipped token-ratio surrogate and a reference-policy KL term. In the original outcome-supervision recipe, each token in a completion receives the same group-relative score. Removing the value model saves its resources; rollout lengths, group size, and other models still determine total cost.

If every completion has the same reward, the normalized reward component is zero; a KL term may still contribute an update. This empirical group-relative statistic differs from the exact $Q^\pi-V^\pi$ advantage. Its group mean includes the sample being updated, and its standard deviation rescales prompt contributions. State which variant, normalization, and length weighting you use when estimating policy gradients.

The bridge is reward-based probability updates over sequences. A better surrogate score doesn't itself prove stronger reasoning, a better verifier, or useful behavior on held-out tasks.

What a policy scorecard can and can't establish

Use an oracle scorecard to check four constructed starting cases against our known environment equations. Each rule below chooses an action in those two starting states; the sole approve_request action at review_queue is fixed. The chosen mixture of two new_request and two evidence_ready cases is part of the calculation, not representative-traffic evidence:

action_values = {
    "new_request": {
        "auto_approve": -120,
        "request_evidence": 30.75,
        "human_review": 54.0,
    },
    "evidence_ready": {"auto_approve": 70, "human_review": 62.0},
}
cases = ["new_request", "new_request", "evidence_ready", "evidence_ready"]
policies = {
    "always_auto": lambda state: "auto_approve",
    "always_review": lambda state: "human_review",
    "risk_aware": lambda state: (
        "human_review" if state == "new_request" else "auto_approve"
    ),
}

for name, policy in policies.items():
    returns = [action_values[state][policy(state)] for state in cases]
    unsupported = sum(
        state == "new_request" and policy(state) == "auto_approve"
        for state in cases
    )
    mean_return = sum(returns) / len(returns)
    if name == "risk_aware":
        assert mean_return == 62.0
        assert unsupported == 0
    if name == "always_review":
        assert mean_return == 58.0
    print(
        f"{name:13} expected mean={mean_return:5.1f} unsupported_approvals={unsupported}"
    )

always_auto   expected mean=-25.0 unsupported_approvals=2
always_review expected mean= 58.0 unsupported_approvals=0
risk_aware    expected mean= 62.0 unsupported_approvals=0

The oracle scorecard knows counterfactual values because we specified the environment equations. In real operations, historical logs record only the action chosen and its resulting outcome. Evaluating an alternate policy $\pi$ from logs collected by a behavior policy $\mu$ requires off-policy evaluation (OPE):

• Importance sampling: Under common dynamics and a common initial-state distribution, an entire episode's return uses the trajectory weight $W=\prod_{t=0}^{T-1}\pi(A_t\mid S_t)/\mu(A_t\mid S_t)$. Per-decision estimators weight each reward by the cumulative product through the action that produced it, not merely that step's ratio.^{[1]Reference 1Reinforcement Learning: An Introductionhttp://incompleteideas.net/book/the-book-2nd.html}
• Coverage requirements: If $\mu(a\mid s)=0$ for an action the target chooses in a reachable state, importance sampling lacks support. A positive propensity with no observed visits is different: theoretical support can hold while a finite log still contains no usable samples for that choice.
• Unmeasured confounding: Private information that affects both action selection and outcomes can invalidate causal evaluation from the recorded states and propensities. This is separate from whether a state representation is Markov.

For two logged decisions with behavior probabilities 0.5, 0.5 and target probabilities 0.8, 0.6, the trajectory weight is (0.8/0.5)*(0.6/0.5)=1.92. Using only the last ratio, 1.2, misses how the first choice changes trajectory frequency. Products can have high variance; a large log doesn't guarantee enough effective samples. Model-based and doubly robust OPE offer other tradeoffs, but don't identify unsupported actions without additional assumptions or evidence.

Record the actual logging propensities, relevant decision-time information, and the desired starting-case distribution. Verify coverage and temporal relevance; a chronological split alone doesn't repair confounding or a misspecified environment.

Stress-test the assumptions

Score a route, back up a state, and notice when a log has no coverage for the action you want to evaluate. Each check below moves one assumption: the abandonment rate, the legal actions, or the actions present in the log.