RL 系列第 5 篇：学习自动机与随机环境（1961–1974）

Quick recap, in case you're jumping in from Blog 4.

• Arthur Samuel's checkers program learned by guessing how good a board position was (value estimation). Donald Michie's matchbox machine, MENACE, learned by shifting which move it preferred (policy selection). Both worked. Both were fragile: Samuel needed hand-crafted features, and Michie needed one matchbox for every possible board.

• That left a question hanging: what is the absolute minimum a machine needs in order to improve from feedback?

The first clean answer came from Moscow.

Before we start: a 60-second jargon cheat sheet

You'll see these words a lot in this post. None of them are scary.

• Agent: the thing that acts and learns (here, a tiny machine).
• Environment: whatever the agent interacts with (here, a set of slot machines).
• Action: a choice the agent can make (which machine to pull).
• Reward / Penalty: the feedback after an action. Good outcome = reward, bad outcome = penalty.
• Stochastic: "random-ish." The same action can give different results on different tries.
• Automaton (plural: automata): a machine that lives in one of a fixed number of states and hops between them by simple rules. Think of a traffic light, not a supercomputer.
• State: which "mode" the machine is currently in. Its memory, basically.

Part 1: The smallest learning machines

The problem: how do you learn when feedback is unreliable?

Samuel and Michie taught us that machines can learn from experience. But both of their systems quietly assumed the feedback made sense. Win the game, good. Lose the game, bad.

Real life is messier. Picture vending machines on your street:

• Machine A gives you a free snack 70% of the time.
• Machine B gives you a free snack 40% of the time.

You don't know these numbers. You can only try a machine, see if it pays, and adjust. And here's the catch: Machine A will sometimes fail you, and Machine B will sometimes get lucky. One result tells you almost nothing.

So the real question becomes: how does a machine learn the right choice when any single outcome might be a lie?

That's the world of stochastic environments, and it's where Mikhail Tsetlin starts.

Meet Mikhail Tsetlin: the "smallest possible brain" guy

Mikhail Tsetlin (1924–1966) was a Soviet mathematician working in Moscow in the era of early cybernetics. In 1961 he published a paper titled "On the behaviour of finite automata in random medium". The title is a mouthful, but the idea is beautifully modest.

Most researchers of the day asked, "how do we build a smarter machine?" Tsetlin asked the opposite question:

What is the smallest internal structure a machine needs to improve its behavior?

Not the most powerful. The smallest. He was hunting for the floor of machine intelligence.

His answer was a finite-state automaton with a twist: no model of the world, no predictions, no calculus, no score. Just:

1. a handful of internal states (its memory),
2. a rule for choosing an action based on the current state, and
3. a rule for moving between states based on feedback.

Note the phrase "random medium" in the title. That's Tsetlin's name for a stochastic environment: a world that answers your actions with reward or penalty according to hidden probabilities. The vending machines are a random medium.

The Rooms: Tsetlin's memory, made visible

The best way to understand a Tsetlin automaton is to picture a hallway of rooms.

• The left half of the hallway is "Action A" (pull machine A).
• The right half is "Action B" (pull machine B).
• The machine is always standing in exactly one room, and whatever side it's on decides what it does next.

Here's a small version with 3 rooms per side (6 states total):

   Action A side              Action B side
 [ 1 ] [ 2 ] [ 3 ] | [ 4 ] [ 5 ] [ 6 ]
  deep        edge  |  edge        deep

The rules are only two lines long:

• Reward -> walk deeper into your current side (more committed).
• Penalty -> walk one room toward the middle. If you were already at the edge, you cross the border and switch actions.

Feedback is just a single bit: 0 = reward, 1 = penalty. No scores, no probabilities, no gradients. Only movement.

Let's walk through it

Say we start in room 3 (the edge of Action A) and keep pulling machine A, which pays 70% of the time:

Look at step 3. The machine got unlucky, but it didn't panic. One bad result only moved it one room, and it was still firmly on Team A. The rooms absorbed the noise.

Why memory matters (why not just flip a coin?)

You might ask: if feedback is just reward/penalty, why bother with six rooms? Why not the simplest rule ever: "if it paid, do it again; if not, switch"?

Funny thing: that rule is a Tsetlin automaton, the smallest one, with only 1 room per side. It's the classic win-stay, lose-shift strategy. And it's jumpy. One unlucky penalty and it abandons a perfectly good machine.

Think of your favorite restaurant. You had one bad meal. Do you never go back? Of course not. You have memory of many good meals, so one bad night doesn't flip your opinion. More rooms = more patience.

So let's test it. I simulated the exact hallway above (Machine A pays 70%, Machine B pays 40%, 5,000 pulls per run, averaged over 200 runs), changing only the number of rooms per side, N:

More memory, better decisions. Here's the tiny code if you want to try it yourself:

import random

def tsetlin(pay=(0.7, 0.4), N=3, steps=5000):
    # states 1..N   -> action 0 (1 = deepest, N = edge)
    # states N+1..2N -> action 1 (N+1 = edge, 2N = deepest)
    state = N
    pulls = [0, 0]
    for _ in range(steps):
        action = 0 if state <= N else 1
        pulls[action] += 1
        rewarded = random.random() < pay[action]
        if action == 0:
            state = max(state - 1, 1) if rewarded else state + 1
        else:
            state = min(state + 1, 2 * N) if rewarded else state - 1
    return pulls

print(tsetlin(N=1), tsetlin(N=10))

Tsetlin proved this trend mathematically. As N grows, the automaton gets arbitrarily close to always picking the best action:

P(best action)→1asN→∞

Two honest footnotes:

• This works when the best action really is better than a coin flip (its penalty probability is below 50%). Our 70% machine qualifies.
• Memory has a price. A deep automaton is stubborn: if the world changes (say, Machine B suddenly gets better), a machine sitting in the deepest room needs many penalties to walk out. Stability and adaptability pull in opposite directions. Remember this tension; it comes back in Part 2.

The catch: rooms don't scale

Tsetlin's automaton is elegant, but notice what it needs: a hand-designed hallway. How many rooms? Which transitions? For two actions it's easy. For a hundred actions you'd be designing a giant state machine by hand.

It's the same flavor of problem we hit in Blog 4: Michie needed a matchbox per board. Tsetlin needed a room per memory level. Someone had to ask: what if we just delete the rooms?

Delete the rooms: Variable-Structure Automata

The idea of replacing rooms with probabilities dates to Soviet researchers Varshavskii and Vorontsova (1963), and similar update rules were being explored in mathematical psychology around the same time. Then in 1974, Kumpati Narendra and M. A. L. Thathachar published a landmark survey, "Learning Automata: A Survey", that organized the whole field, gave it its name in the West, and split it into two families:

1. Fixed-Structure Automata (FSA): Tsetlin's world.
The hallway is fixed. Learning = moving through rooms. Where you go next depends only on where you are now and whether you were just rewarded or penalized.

2. Variable-Structure Automata (VSA): throw away the house.
No rooms at all. Instead the machine keeps a list of probabilities, one per action, that always adds up to 100%. Like a set of volume knobs where turning one up turns the others down.

Learning becomes: "that worked, so turn its knob up a bit."

The volume-knob rule, with real numbers

Let p_i be the probability of picking action i, and λ (lambda) a small "step size" called the learning rate. When the chosen action i is rewarded:

pi←pi+λ (1−pi)

and every other action j is nudged down so the total stays at 1:

pj←(1−λ) pj

Concrete example with 3 actions, p = [0.50, 0.30, 0.20], λ = 0.1, and action 1 gets rewarded:

• Action 1: 0.50 + 0.1 x (1 - 0.50) = 0.55
• Action 2: 0.30 x 0.9 = 0.27
• Action 3: 0.20 x 0.9 = 0.18
• New total: 0.55 + 0.27 + 0.18 = 1.00 ✓

If the same action is penalized instead, the mirror-image rule turns its knob down and spreads that probability over the others:

pi←(1−λ) pi,pj←λr−1+(1−λ) pj

(r is the number of actions.) With our example: action 1 drops to 0.45, action 2 rises to 0.32, action 3 to 0.23. Still totals 1.

Notice something? No rooms, no transition table, no memory hallway. The probability list is the memory. One small rule replaced a whole state machine.

Why this matters for modern RL

This is where the old Soviet-era ideas quietly show up in today's algorithms.

"Raise the probability of what worked" is the heart of policy gradient methods (we'll get there properly in Blog 10). Ronald Williams's REINFORCE algorithm (1992) is a direct descendant, and Williams himself showed that a learning automaton can be viewed as a special case of REINFORCE. It's the volume knob again, just dressed up with gradients so it can tune millions of parameters instead of three numbers.

Tsetlin's rooms have a living descendant too. In 2018, Ole-Christoffer Granmo introduced the Tsetlin Machine, which uses teams of Tsetlin automata to learn human-readable logic rules from data. It's a rare case of a 1961 idea being revived as a modern machine-learning method, notable for being interpretable and cheap to run.

And the same tension keeps returning. Tsetlin's "memory = stability, but also stubbornness" is the modern stability-vs-adaptability problem that every RL practitioner still wrestles with.

Tsetlin vs. Narendra: two halves of one answer

Together they gave the field its first solid answer to Tsetlin's question: a machine can improve from nothing but feedback, with no model of the world.

Part 2: The puzzle behind it all, the Multi-Armed Bandit

Zoom out: you've been solving a famous problem

What you just saw, a row of slot machines with unknown payouts and a limited number of pulls, is famously called the Multi-Armed Bandit problem ("one-armed bandit" is old slang for a slot machine). The idea goes back to Thompson (1933), who asked how to split patients between two treatments, and the statistician Herbert Robbins formalized it in 1952. Tsetlin's random-medium experiments attacked the same core dilemma from an automata angle.

It is the cleanest version of the exploration vs. exploitation trade-off we met in Blog 4 with Samuel:

• Exploit: keep pulling the machine that seems best.
• Explore: try another one, in case it's actually better.

Interesting detail: a Tsetlin automaton never decides to explore. Noise does it for it. Occasional penalties push it toward the boundary, and it sometimes tries the other side. Exploration falls out of the structure for free.

Rooms and volume knobs are two ways to play this game. Engineers have since built sharper ones. To compare them fairly, we first need to state the problem cleanly.

The setup

You face K machines (called arms). Arm a pays out according to some fixed, unknown average μ_a. At every step t = 1, 2, ..., T you pick one arm and see the reward from that arm only. Your goal: collect as much total reward as possible over T steps.

Two things make this hard:

1. You only see the arm you pulled. You never learn what the other arms would have paid.
2. Your data depends on your choices. If you stop pulling an arm, you stop learning about it. A bad first impression can become permanent.

Scored, not taught

Compare this to supervised learning, where a teacher hands the machine the right answer ("this image is a cat"). A bandit gets no such answer. It only gets a score for what it did ("that ad got a click") and no hint about whether something else would have scored higher. The only way to find out is to try other things. Sutton and Barto call this evaluative feedback, and it's the reason exploration exists at all.

Why bandits matter

1. They isolate exploration vs. exploitation. One situation, no delayed consequences, so you can study the dilemma in its purest form.
2. They score you while you learn. Not "how accurate is the model after training," but "how much did you lose along the way." That score is called regret, coming up next.

A few new words

• Arm: one choice you can make (a slot machine, an ad, a headline).
• Q(a): your running estimate of how good arm a is.
• Gap (Δ): how much worse an arm is than the best arm.
• Regret: the total reward you lost by not always playing the best arm.
• Posterior: your belief about an arm's true payout after seeing data. Wide = unsure. Narrow = confident.

Two tools you need: estimating and keeping score

Estimating an arm's value, one pull at a time

After n pulls of an arm, the average reward is Q_n = (R_1 + R_2 + ... + R_n) / n. You never need to store the history. Rearranging gives an update that shows up everywhere in RL:

Qn+1=Qn+1n (Rn−Qn)

In words: new estimate = old estimate + step size x (target - old estimate).

Now swap the 1/n for a constant α. Old rewards fade out gradually, so you track a moving target instead of a fixed one. That's how you cope with a world that changes (we'll see the payoff in the practical section).

Qn+1=Qn+α (Rn−Qn)

Remember the volume knob? The reward rule p ← p + λ(1 - p) from earlier is this exact update with target 1. Same idea, different clothes.

Regret: the scoreboard

Let μ* be the average payout of the best arm and Δ_a = μ* - μ_a the gap of arm a. After T steps, the regret is how much you earned less than someone who knew the best arm from the start:

RT  =  Tμ∗−E[∑t=1TRt]  =  ∑a: Δa>0Δa E[NT(a)]

(E[...] just means "on average," and N_T(a) is how many times you pulled arm a.) The second form is the useful one: regret = (cost per bad pull) x (number of bad pulls).

Quick example with our vending machines: the gap between A (70%) and B (40%) is 0.3. Every pull of B costs you 0.3 snacks on average, so 100 pulls of B means about 30 snacks of regret. To keep regret low you must pull bad arms as rarely as possible, but you can't skip them entirely, or you'd never know they were bad.

How should regret grow over time?

• Linear in T: you never stopped making mistakes. Failure.
• Logarithmic in T: mistakes become rarer and rarer, so regret grows slower and slower. This is the best anyone can do, which Lai and Robbins proved in 1985.

One more intuition worth keeping: the closer two options are, the longer it takes to tell them apart, and the more exploring you must pay for. Telling a 70% machine from a 40% one is easy. Telling 12% from 15% takes thousands of pulls.

The strategy zoo

Now the fun part. We'll go through the main strategies, each with its rule, its intuition, its math, and where it breaks.

1. Greedy: always pick the best-looking arm

At=arg⁡max⁡aQt(a)

Simple, and broken. A single lucky early pull on a mediocre arm can make its estimate look best, and since pure greedy never samples anything else, it locks onto that arm forever. That's linear regret, caused by zero exploration.

2. ε-greedy: add some randomness

With probability 1 - ε pick the best-looking arm; with probability ε pick uniformly at random. Dead simple and a great baseline.

Its flaw is mathematical: random exploration continues forever, even when you're certain. Because ε stays fixed (say, 0.10), each arm is chosen with probability at least ε/K at every step, which gives:

RT  ≥  ϵK(∑aΔa) T

That's linear regret. A fixed ε is a permanent tax: even after 1,000,000 pulls, when you know exactly which arm is best, you still waste about 10% of pulls on random choices. (Shrinking ε over time can fix this, but then you have a schedule to tune.)

3. Optimistic initialization: let disappointment drive exploration

Start every estimate absurdly high, for example Q_1(a) = +5 when real rewards range from 0 to 1. Every arm you try then "disappoints" compared to that starting hope, so the greedy rule naturally moves on to the untried arms. It's a clever, nearly free trick that gets a purely greedy algorithm to try everything without any random choices.

The catch: once every arm has been sampled enough, the optimism is gone and the estimates settle at their true averages. If the world changes later (a bad machine suddenly starts paying well), the agent won't re-investigate, because that machine's estimate was pushed down long ago. It only drives exploration during the opening phase.

4. UCB: optimism in the face of uncertainty

UCB (Upper Confidence Bound) is the first strategy built on rigorous probability theory. Instead of picking the arm with the best average, you pick the arm with the best plausible upper bound: its estimate plus an uncertainty bonus.

At=arg⁡max⁡a[Qt(a)+cln⁡tNt(a)]

How the bonus behaves:

• It shrinks with experience. The more you pull an arm (N grows), the smaller its bonus, because its average is already trustworthy.
• It grows with time. As t ticks forward, the bonus creeps up for neglected arms, so every option eventually gets another look.

A worked example (using c = 1 to keep things simple; at step t = 200):

Arm A has the better average, but UCB plays Arm B, because with only 10 pulls it might still be hiding something great. Pull B a few more times and its bonus shrinks; if its average stays low, A takes over again. Exploration shrinks exactly as fast as your doubt does.

5. Thompson Sampling: let each arm "vote" with a random draw

Thompson's 1933 algorithm is surprisingly simple, and works remarkably well:

1. Keep a posterior (a curve showing how confident you are about each arm's payout).
2. Draw one random sample from each arm's curve.
3. Play the arm whose sample is highest.

For yes/no outcomes (clicks vs. no clicks), the natural curve is the Beta distribution. You start with a flat Beta(1, 1) ("total uncertainty"). After s successes and f failures, it becomes Beta(1 + s, 1 + f).

Worked example

Two ads show roughly the same 30% click rate, but with very different amounts of evidence:

Similar averages, wildly different certainty:

How self-correcting exploration works

Because Ad X has a wide, uncertain curve, its random draws beat Ad Y's about 58% of the time. That balances exploring and exploiting automatically:

• Exploitation (Ad Y): a reliable performer with high confidence, a stable baseline.
• Exploration (Ad X): unproven. It could turn out to be a weak ad or a game-changer, and the width of its curve is the potential upside of learning more.
• Automatic feedback loop:
  • If Ad X's future impressions fail to convert, its curve shifts left and narrows, so it loses future draws and drops out of rotation.
  • If Ad X keeps converting, its curve narrows around a high mean and it becomes the new winner.

Thompson Sampling spends exploration effort in proportion to uncertainty, with almost no tuning (no c, no ε).

6. Gradient bandits: learn preferences, not values

Instead of estimating how good each arm is, learn a numerical preference H(a) and turn preferences into probabilities with a softmax (a recipe that turns any list of numbers into probabilities that add up to 1):

πt(a)=eHt(a)∑beHt(b)

After pulling A_t and receiving R_t, update, using the running average reward R̄_t as a baseline ("what I normally get"):

Ht+1(a)=Ht(a)+α (Rt−Rˉt) (1[a=At]−πt(a))

In plain words: better than usual? Push the chosen arm's preference up and the others down. Worse than usual? The reverse. (Mathematically this is gradient ascent on average reward, and the baseline keeps the updates from being too jumpy.)

Back to Part 1, and a preview of Blog 10: this is the volume-knob idea again ("raise the probability of what worked"), now with a gradient. Bandits are where policy gradients start.

Let's measure them

Theory is nice. Here's what actually happens. I ran two experiments.

Experiment 1: the classic 10-armed testbed. Each run draws 10 arm averages at random, rewards are noisy around those averages, 1,000 steps, averaged over 1,000 runs:

Two honest footnotes:
(1) Thompson's starting beliefs here exactly match how the arms were generated, which flatters it, so don't expect a 2x regret win in the wild;
(2) c = 2 uses the Sutton-Barto form c·√(ln t / N), and c is a tuning knob.

Experiment 2: how does regret grow? Five arms with success rates 0.10, 0.12, 0.15, 0.20, 0.25 (small gaps, like real conversion rates), averaged over 40 runs:

Read this one slowly, because it teaches something the textbooks gloss over:

• ε-greedy's regret grows at a constant slope (about 0.0086 per step between 5k and 20k), matching the (ε/K)ΣΔ floor we derived. It will lose in the long run.
• UCB1 is worse than ε-greedy at this horizon. Its "grows slower and slower" guarantee is real, but its constants are conservative, and its slope (about 0.014 per step here) is still shrinking. "Best in the long run" does not mean "best at your horizon."
• Thompson's slope is about 0.001 per step. Nearly flat. That's why you see it so often in production.

A reference implementation

Small enough to read in one sitting, tested to produce the numbers above:

import numpy as np

class EpsGreedy:
    def __init__(self, K, eps=0.1, alpha=None):
        self.eps, self.alpha = eps, alpha
        self.Q, self.N = np.zeros(K), np.zeros(K)
    def select(self, t):
        if np.random.rand() < self.eps:
            return np.random.randint(len(self.Q))
        return int(self.Q.argmax())
    def update(self, a, r):
        self.N[a] += 1
        step = self.alpha if self.alpha else 1.0 / self.N[a]   # alpha => non-stationary
        self.Q[a] += step * (r - self.Q[a])

class UCB1:
    def __init__(self, K, c=np.sqrt(2)):
        self.c, self.Q, self.N = c, np.zeros(K), np.zeros(K)
    def select(self, t):                      # t starts at 1
        if (self.N == 0).any():
            return int(np.argmin(self.N))     # play every arm once first
        return int((self.Q + self.c * np.sqrt(np.log(t) / self.N)).argmax())
    def update(self, a, r):
        self.N[a] += 1
        self.Q[a] += (r - self.Q[a]) / self.N[a]

class ThompsonBernoulli:
    def __init__(self, K):
        self.wins, self.losses = np.ones(K), np.ones(K)    # Beta(1,1) prior
    def select(self, t):
        return int(np.random.beta(self.wins, self.losses).argmax())
    def update(self, a, r):
        if r: self.wins[a] += 1
        else: self.losses[a] += 1

def run(agent, probs, T):
    best, regret = max(probs), 0.0
    for t in range(1, T + 1):
        a = agent.select(t)
        r = np.random.rand() < probs[a]
        agent.update(a, r)
        regret += best - probs[a]
    return regret

print(run(ThompsonBernoulli(5), [0.10, 0.12, 0.15, 0.20, 0.25], 20000))

The practical corner: using a bandit for real

When a bandit is the right tool

• Feedback is immediate. You act, you get a number, and your action doesn't change what situations you'll face next.
• Showing the loser has a real cost. Every user sent to a worse option is lost revenue, clicks, or goodwill.
• Choices are discrete and few-ish. Headlines, layouts, models, prompts, settings.
• You'll keep running it. A bandit is a loop, not a one-off analysis.

when the world changes

Five arms with success rates 0.2, 0.3, 0.4, 0.5, 0.7 for 4,000 steps, and at step 2,000 the order is reversed, so the best arm becomes the worst. Total reward, averaged over 500 runs:

The plain average never recovers: after 2,000 steps its estimates are so weighed down by history that new evidence barely moves them. Switching to a constant step size, a one-line change, won back about 770 reward. This is Tsetlin's stability-vs-adaptability tension again, now with a dial you control.

Choosing an algorithm

Where it all runs out of road

So, problem solved? Not quite. Learning automata and bandits share two big blind spots:

1. They don't see the situation, and they don't change it. The machine picks an action, but it never observes anything about the world first. There's no "if the board looks like this, do that." A vending machine is always the same vending machine, and pulling its lever doesn't change what comes next. Real problems change from moment to moment: chess boards, road conditions, the words already written in a sentence. (If you only add the "look at the situation first" part, you get a contextual bandit, which is a halfway house between bandits and full RL. If your actions also change the next situation, you've left bandit territory entirely.)

2. They only understand immediate feedback. Every update reacts to the reward right now for the action just taken. But in most interesting problems, consequences arrive late:

• A chess move that quietly weakens your position may not cost you the game for 20 turns.
• A financial decision may not show its results for months.
• A word you choose early in a sentence shapes everything after it.

The machine would have to guess which of its past actions deserves the blame or credit. It has no mechanism for that. This is the famous credit assignment problem, and it is the gap the next era of RL sets out to fill. (Samuel's checkers program from Blog 4 was already sniffing around this problem. Its temporal-difference trick gets its full moment later in the series.)

Quick recap

• Question: what is the smallest structure that lets a machine improve from feedback?
• Tsetlin (1961): a hallway of rooms. Reward = go deeper, penalty = step back. More rooms = more stability, but also more stubbornness.
• Variable-structure automata (1963-1974): delete the rooms, keep a probability per action, and nudge it up or down with feedback. This is the seed of policy gradients.
• Both are ways of playing the multi-armed bandit, the cleanest version of exploring vs. exploiting.
• Regret (reward lost vs. always playing the best arm) is the scoreboard. Linear = failing, logarithmic = best possible.
• The toolkit: ε-greedy (simple, permanent exploration tax), UCB (optimism about what you haven't tried), Thompson sampling (explore in proportion to doubt, great in practice), gradient bandits (learn preferences, the cousin of policy gradients).
• In practice: a bandit beat a fixed A/B split by roughly 4x in lost conversions in our simulation, and a constant step size won back ~770 reward after the world flipped.
• Blind spots: no awareness of the situation, and no way to handle delayed rewards.

Up next

So machines can now adapt reliably to noisy feedback. But what if the feedback comes late, and what if the "learner" isn't a tidy algorithm at all, but a neuron? In the 1970s, Harry Klopf proposed exactly that: neurons as tiny, pleasure-seeking units. Around the same time, Paul Werbos quietly described an idea that would later be famous as backpropagation.

Next: Blog 6 - The "Hedonistic" Revival: Klopf's Pleasure-Seeking Neurons and Werbos's Hidden Backpropagation (1972-1980).