從 MDP 到 Q-learning：行動如何影響後續報酬？

p(s′, r | s, a)

0 --R, −0.1--> 1 --R, −0.1--> 2 --R, +1--> goal

G₀ = R₁ + γR₂ + γ²R₃
   = −0.1 + 0.9×(−0.1) + 0.9²×1
   = 0.62

G_t = R_(t+1) + γR_(t+2) + γ²R_(t+3) + ...
    = R_(t+1) + γG_(t+1)

Q*(s,a) = Σ_(s′,r) p(s′,r | s,a)
          × [r + γ max_b Q*(s′,b)]

若該轉移真正終止，方括號只剩 r。

V*(2) = 1
V*(1) = −0.1 + 0.9×1   = 0.8
V*(0) = −0.1 + 0.9×0.8 = 0.62

Q*(0,L) = −1                    （進 trap，終止）
Q*(1,L) = −0.1 + 0.9×0.62 = 0.458
Q*(2,L) = −0.1 + 0.9×0.8  = 0.62

target = r + γ max_b Q(s′,b)     （非終止）
TD error = target − Q(s,a)
Q(s,a) ← Q(s,a) + α × TD error

Q(0,L) = 0 + 0.2×(−1−0) = −0.2

terminated = True：target只用r
truncated，但terminated = False：仍用r + γ maxQ(next_state)

# Python 3.10.12; standard library only. No third-party packages required.

python3 tabular_q_learning.py > stdout.json

"""Original deterministic tabular MDP; standard-library mechanics, not a maze benchmark."""
import json
import math
import platform
import random


NONTERMINAL_STATES = (0, 1, 2)
ACTIONS = (0, 1)  # L=0, R=1
GOAL, TRAP = 3, 4
GAMMA, ALPHA, EPSILON = 0.9, 0.2, 0.2
SEED, EPISODES, MAX_STEPS = 7, 2000, 20


def argmax_low_id(row):
    return max(range(len(row)), key=lambda action: row[action])


def environment_step(state, action):
    """Only the environment/evaluator uses this complete transition model."""
    transitions = {
        (0, 0): (TRAP, -1.0, True),
        (0, 1): (1, -0.1, False),
        (1, 0): (0, -0.1, False),
        (1, 1): (2, -0.1, False),
        (2, 0): (1, -0.1, False),
        (2, 1): (GOAL, 1.0, True),
    }
    if (state, action) not in transitions:
        raise ValueError("Step accepts only nonterminal states0..2 and actions0..1")
    return transitions[state, action]


class QLearner:
    def __init__(self, seed):
        self.q = [[0.0, 0.0] for _ in NONTERMINAL_STATES]
        self.visits = [[0, 0] for _ in NONTERMINAL_STATES]
        self.rng = random.Random(seed)

    def choose(self, state):
        if self.rng.random() < EPSILON:
            # Random branch includes the greedy action as well.
            return self.rng.randrange(len(ACTIONS))
        return argmax_low_id(self.q[state])

    def observe(self, state, action, reward, next_state, terminated):
        # A true terminal has no continuation. Time-limit truncation is NOT terminal.
        bootstrap = 0.0 if terminated else max(self.q[next_state])
        target = reward + GAMMA * bootstrap
        before = self.q[state][action]
        td_error = target - before
        after = before + ALPHA * td_error
        self.q[state][action] = after
        self.visits[state][action] += 1
        return {"state": state, "action": action, "reward": reward,
            "next_state": next_state, "terminated": terminated,
            "old_q": before, "bootstrap_max_q": bootstrap,
            "target": target, "td_error": td_error, "new_q": after}


def model_oracle():
    """Synchronous Bellman iteration using the known model, separate from the learner."""
    q = [[0.0, 0.0] for _ in NONTERMINAL_STATES]
    for sweep in range(1, 1001):
        updated = []
        for state in NONTERMINAL_STATES:
            row = []
            for action in ACTIONS:
                next_state, reward, terminated = environment_step(state, action)
                row.append(reward if terminated else reward + GAMMA * max(q[next_state]))
            updated.append(row)
        change = max(abs(updated[s][a] - q[s][a]) for s in NONTERMINAL_STATES for a in ACTIONS)
        q = updated
        if change < 1e-14:
            return q, sweep
    raise RuntimeError("Oracle iteration did not stabilize")


def evaluate_greedy(q):
    state = 0
    trajectory = []
    for time_index in range(MAX_STEPS):
        action = argmax_low_id(q[state])
        next_state, reward, terminated = environment_step(state, action)
        trajectory.append({"state": state, "action": action, "reward": reward,
                           "next_state": next_state, "terminated": terminated})
        state = next_state
        if terminated:
            break
    return {"trajectory": trajectory,
        "undiscounted_return": math.fsum(x["reward"] for x in trajectory),
        "discounted_return": math.fsum(GAMMA**t * x["reward"] for t, x in enumerate(trajectory)),
        "terminated": trajectory[-1]["terminated"],
        "truncated": not trajectory[-1]["terminated"] and len(trajectory) == MAX_STEPS}


def main():
    learner = QLearner(SEED)
    endings = {"goal": 0, "trap": 0, "truncated": 0}
    terminal_samples = {"goal": [], "trap": []}
    truncation_samples = []
    first_episode_transitions = []
    episode_lengths = []
    episode_returns = []
    for episode in range(EPISODES):
        state = 0
        rewards = []
        for step in range(1, MAX_STEPS + 1):
            action = learner.choose(state)
            next_state, reward, terminated = environment_step(state, action)
            # This flag controls the collector/reset only, not the Bellman target.
            truncated = step == MAX_STEPS and not terminated
            update = learner.observe(state, action, reward, next_state, terminated)
            rewards.append(reward)
            record = {"episode_0_based": episode, "step_1_based": step,
                      "truncated": truncated, **update}
            if episode == 0:
                first_episode_transitions.append(record)
            if terminated:
                kind = "goal" if next_state == GOAL else "trap"
                endings[kind] += 1
                if len(terminal_samples[kind]) < 3:
                    terminal_samples[kind].append(record)
                break
            if truncated:
                endings["truncated"] += 1
                if len(truncation_samples) < 3:
                    truncation_samples.append(record)
                break
            state = next_state
        episode_lengths.append(len(rewards))
        episode_returns.append(math.fsum(rewards))
    oracle_q, sweeps = model_oracle()
    max_error = max(abs(learner.q[s][a] - oracle_q[s][a])
                    for s in NONTERMINAL_STATES for a in ACTIONS)
    greedy_evaluation = evaluate_greedy(learner.q)
    # A controlled nonzero continuation example, NOT an extra training episode.
    check = QLearner(0)
    check.q = [row[:] for row in oracle_q]
    truncation_check = check.observe(0, 1, -0.1, 1, False)
    next_q = oracle_q[1]
    greedy_action = argmax_low_id(next_q)
    behavior_probabilities = [EPSILON / 2 + (1 - EPSILON if a == greedy_action else 0)
                              for a in ACTIONS]
    comparison = {"transition": {"state": 0, "action": 1, "reward": -0.1, "next_state": 1},
        "next_state_q_values": next_q,
        "epsilon_behavior_probabilities_L_R": behavior_probabilities,
        "q_learning_target_using_max": -0.1 + GAMMA * max(next_q),
        "sarsa_target_if_next_behavior_action_is_L": -0.1 + GAMMA * next_q[0],
        "expected_behavior_target_for_comparison_only": -0.1 + GAMMA * math.fsum(
            p * q for p, q in zip(behavior_probabilities, next_q))}
    assert sum(endings.values()) == EPISODES
    assert sum(map(sum, learner.visits)) == sum(episode_lengths)
    assert all(n > 0 for row in learner.visits for n in row)
    assert max_error < 1e-10
    assert [x["action"] for x in greedy_evaluation["trajectory"]] == [1, 1, 1]
    assert math.isclose(greedy_evaluation["undiscounted_return"], .8)
    assert math.isclose(greedy_evaluation["discounted_return"], .62)
    print(json.dumps({
        "scope": "Original small deterministic tabular MDP; actual2000trainingepisodes, "
                 "not a maze reproduction, policy benchmark, or finite-run convergence theorem.",
        "versions": {"python": platform.python_version(), "dependencies": "standard library only"},
        "settings": {"nonterminal_states": NONTERMINAL_STATES, "goal": GOAL, "trap": TRAP,
            "actions": {"L": 0, "R": 1}, "gamma": GAMMA, "alpha": ALPHA, "epsilon": EPSILON,
            "seed": SEED, "episodes": EPISODES, "collector_max_steps": MAX_STEPS,
            "start_state_every_episode": 0, "initial_q": "all six entries zero",
            "tie_break": "lowest action ID", "epsilon_branch": "uniform over both actions",
            "update": "Q(s,a) += alpha*(r + gamma*maxQ(next) - Q(s,a)); no continuation for true terminals",
            "truncation": "time limit resets collector only; bootstrap from observed next state retained"},
        "model_for_reader_and_oracle_only": [
            {"state": s, "action": a, "next_state": environment_step(s, a)[0],
             "reward": environment_step(s, a)[1], "terminated": environment_step(s, a)[2]}
            for s in NONTERMINAL_STATES for a in ACTIONS],
        "training": {"episode_endings": endings, "total_observed_transitions": sum(episode_lengths),
            "state_action_visit_counts_L_R": learner.visits,
            "mean_episode_length": math.fsum(episode_lengths) / EPISODES,
            "mean_undiscounted_episode_return": math.fsum(episode_returns) / EPISODES,
            "first_episode_transitions": first_episode_transitions,
            "first_terminal_updates": terminal_samples,
            "first_observed_truncation_updates": truncation_samples},
        "learned_q_L_R": learner.q,
        "model_oracle": {"q_L_R": oracle_q, "synchronous_sweeps": sweeps,
            "optimal_v": [max(row) for row in oracle_q], "max_learned_abs_error": max_error,
            "role": "Known transition model only used AFTER training for evaluation, never learner update/choice"},
        "greedy_evaluation_no_learning_no_exploration": greedy_evaluation,
        "controlled_truncation_example_not_training": {
            "description": "At time limit after 0R->1, next state1 is not terminal; continue bootstrapping",
            "correct_update": truncation_check,
            "wrong_target_if_truncation_mistaken_for_terminal": -0.1},
        "behavior_vs_target_arithmetic_not_sarsa_training": comparison,
        "limits": ["Learner receives only observed state/action/reward/nextstate/terminated tuples, not the model.",
            "Fixed2000episodes and alpha.2 do not satisfy the decreasing-step-size convergence theorem in general.",
            "All six pairs were visited in this run; finite positive visits are not infinite exploration.",
            "Goal/trap terminal value is zero; terminal Q rows are not stored or read.",
            "Collector truncation is exogenous, not a finite-horizon MDP terminal or a learned reset transition.",
            "If time remaining changed the actual task objective, it would need to be included in the state.",
            "Greedy evaluation freezes Q and removes epsilon exploration; it differs from training behavior.",
            "An epsilon random branch may choose the greedy action; action probabilities are .9/.1 with unique best.",
            "Oracle uses known deterministic transitions; it is a separate model-based reference, not model-free training.",
            "Single seed, hand-designed rewards, no heldout tuning, stochastic environment, function approximation or real-world lift."]}, indent=2))


if __name__ == "__main__":
    main()

DS67 selected illustrations: source attribution and changes

1. Agent–environment loop
OpenAI, Spinning Up, “Introduction to Reinforcement Learning,” https://spinningup.openai.com/en/latest/spinningup/rl_intro.html ; source file https://github.com/openai/spinningup/blob/038665d62d569055401d91856abb287263096178/docs/images/rl_diagram_transparent_bg.png . Copyright (c) 2018 OpenAI. The source PNG was alpha-composited on white; no crop, label or data was added. The full MIT license is reproduced below.

2. MDP transition graph and cover
Waldoalvarez, “Markov Decision Process.svg,” https://commons.wikimedia.org/wiki/File:Markov_Decision_Process.svg , CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/ . The whole vector was rendered on white as a PNG; the cover is the same complete graph fitted proportionally on a white canvas. Changes: SVG-to-PNG render, white background, and cover scaling only. The source’s +5 and −1 labels mark transition rewards, not terminal states. This derivative is released under CC BY-SA 4.0.

3. Q-grid action-value illustration
Fschwarzentruber, “Qlearning gridworld Q.png,” https://commons.wikimedia.org/wiki/File:Qlearning_gridworld_Q.png , CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/ . The whole source PNG was alpha-composited on white without changes to values, arrows or labels. The linked French Wikipedia caption explains darker arrows as larger Q(s,a) values and filled green arrows as maxima; this illustration is not a reported training trace. This derivative is released under CC BY-SA 4.0.

4. Q-learning update formula
Wikimedia contributors, “Q-learning,” French Wikipedia, revision 239118544, https://fr.wikipedia.org/w/index.php?title=Q-learning&oldid=239118544 ; page history https://fr.wikipedia.org/w/index.php?title=Q-learning&action=history ; CC BY-SA 4.0 page terms, https://creativecommons.org/licenses/by-sa/4.0/ . The displayed formula is the page’s ordinary Q-learning update (math element mwdA), rendered from the page math markup by Wikimedia’s math renderer, then rendered as a PNG at 804×99. No formula text was transcribed or altered. This math image is a faithful rendering of the page’s licensed mathematical text; the adapted PNG is provided under CC BY-SA 4.0. This does not extend the page-text license to unrelated external images. The formula is generic and does not itself show terminal masking.

5. Initialized Q table panel
LearnDataSci, “Q-Learning Matrix Initialized and After Training.png,” https://commons.wikimedia.org/wiki/File:Q-Learning_Matrix_Initialized_and_After_Training.png , CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/ . Only the complete top “Initialized” panel was excerpted from the 1000×1016 source image using source-pixel box [0,0,1000,480]; no table value was changed or added. The training arrow and entire post-training panel are excluded. This derivative is released under CC BY-SA 4.0. The tutorial linked on the Commons file page is by Satwik Kansal and Brendan Martin: https://www.learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/ .

The CC BY-SA derivatives listed above are provided under CC BY-SA 4.0 with their respective attribution and changes retained.

Full MIT license for item 1

The MIT License

Copyright (c) 2018 OpenAI (http://openai.com)

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.