Tic-Tac-Toe — Reinforcement Learning Agent (Temporal-Difference Learning)

Sutton & Barto introduce tic-tac-toe as a motivating example for reinforcement learning. The classical approach to this game is minimaxA game-tree search algorithm that picks the move maximizing the worst-case outcome, assuming both players play perfectly. It guarantees optimal play against an optimal opponent, but cannot adapt to or exploit a weaker opponent’s mistakes because it doesn’t learn from experience., which computes optimal play by assuming both players act perfectly. But minimax cannot exploit an imperfect opponent's mistakes — it plays the same way regardless of who it faces. An evolutionaryEvolutionary methods treat each policy (strategy) as an individual in a population. Policies that win more games are selected and mutated to produce the next generation. The drawback: only the final win/loss signal is used, discarding all the information from individual moves within a game. method could search the space of policies directly, but it only uses the final outcome of each game, discarding the information available during play.

The RL approach instead learns a value functionA function V(s) that assigns a number to each state s, estimating how good it is to be in that state. Here, V(s) estimates the probability of winning from board state s. States where you’re about to win have V ≈ 1; states where you’re about to lose have V ≈ 0. V(s) that estimates the probability of winning from each board state s. Specifically, the agent evaluates afterstatesAn afterstate is the board position that results immediately after the agent places its mark, but before the opponent responds. Evaluating afterstates instead of state-action pairs is more efficient because different actions from different positions can produce the same board layout, so the agent can share learned values across those situations. — the board positions that result after the agent places its mark but before the opponent responds. This is efficient because different actions from different prior states can lead to the same afterstate.

The agent uses an ε-greedyA simple exploration strategy: with probability ε (e.g. 0.1 = 10% of the time), pick a random move to explore new board states. The rest of the time (1−ε), pick the greedy move — the one leading to the highest-valued afterstate. Without exploration, the agent may never discover better strategies. policy: with probability ε it makes a random exploratoryAn exploratory move is chosen randomly rather than by the value function. This ensures the agent visits states it might otherwise overlook. Crucially, TD backups are not performed after exploratory moves, because the move wasn’t chosen for its value — updating would inject noise from a random decision. move; otherwise it makes the greedyA greedy move picks the action whose resulting afterstate has the highest estimated value V(s). It’s the agent’s current “best guess” move. TD learning updates happen after greedy moves because they reflect the agent’s actual strategy. move — the one leading to the afterstate with the highest estimated value. After each greedy move, the value estimate is updated using temporal-difference (TD) learningTD learning updates value estimates after every move by comparing the current estimate V(S_t) with the estimate at the next state V(S_t+1). The key idea: instead of waiting until the game ends (like Monte Carlo), TD uses the next state’s estimate as a target. This bootstrapping approach learns faster because every move provides a learning signal.. Exploratory moves are not backed upIn RL, a “backup” is the process of updating a state’s value estimate using information from a successor state. The value of the current state is revised (“backed up”) to be more consistent with what the agent observed next. In TD learning, each greedy move triggers a one-step backup: V(S_t) is nudged toward V(S_t+1). — because they were chosen randomly rather than by the value function, including them would inject noise from decisions that don’t reflect the agent’s learned strategy. The update rule is:

Here S_t is the previous afterstate, S_t+1 is the current afterstate, and α is the step-size parameterAlso called the learning rate. Controls how much each update shifts the value estimate. Large α (e.g. 0.5) means fast but noisy learning; small α (e.g. 0.01) means slow but stable convergence. A value of 0.1 is a common starting point. controlling learning speed. The quantity V(S_t+1) − V(S_t) is the TD errorThe “surprise” signal that drives learning: δ = V(S_t+1) − V(S_t). If the next state has a higher value than expected, δ > 0 and the current state’s value is nudged up. If lower, δ < 0 and the value is nudged down. Over time, these corrections propagate backward through the game.: the difference between successive value estimates that drives learning. Over many games, these values convergeConvergence means the value estimates stop changing significantly between updates. For tic-tac-toe, this typically happens after several thousand self-play games. The values settle to the true winning probabilities under the current policy. to the true winning probabilities and the agent learns to play optimally against its training opponent.