Evaluating agents' behaviors
TD and Monte Carlo: estimating a policy's value from experience.
This lesson combines two challenges: sequential and evaluative feedback. The goal is to estimate the value of a given policy without knowing the MDP — the prediction problem.
The example compares TD(0) and Monte Carlo on a random walk whose true values are known.
Monte Carlo (MC)Wait until the episode ends and use the real return G. Unbiased but high variance
Temporal-difference (TD)Update every step using the estimate of the next state (bootstrapping). Low variance but biased
MC : V(s) ← V(s) + α [ Gₜ − V(s) ]
TD : V(s) ← V(s) + α [ rₜ₊₁ + γ·V(sₜ₊₁) − V(s) ]
└──── TD target ────┘
└──────── TD error ─────────┘
- n-step TD: use n real rewards, then bootstrap. n=1 is TD, n=∞ is MC
- TD(λ): blends every n with weight λ using eligibility traces
Key takeaways
- MC ↔ TD are two ends of one line: low bias/high variance ↔ high bias/low variance
- The TD error is at the heart of almost every algorithm that follows
import numpy as np
# Random walk 7 ຊ່ອງ: 0 ແລະ 6 ແມ່ນຈຸດຈົບ, ໄປຮອດ 6 ໄດ້ +1
rng = np.random.default_rng(0)
def episode():
s, traj = 3, []
while s not in (0, 6):
s2 = s + rng.choice([-1, 1])
traj.append((s, 1.0 if s2 == 6 else 0.0, s2))
s = s2
return traj
def td0(n_episodes=5000, alpha=0.01, gamma=1.0):
V = np.zeros(7)
for _ in range(n_episodes):
for s, r, s2 in episode():
target = r + gamma * V[s2] # TD target (bootstrap)
V[s] += alpha * (target - V[s]) # TD error × learning rate
return V
def monte_carlo(n_episodes=5000):
V, N = np.zeros(7), np.zeros(7)
for _ in range(n_episodes):
traj = episode()
G = traj[-1][1] # γ=1, ລາງວັນມີແຕ່ຕອນທ້າຍ
for s in {s for s, _, _ in traj}: # first-visit MC
N[s] += 1
V[s] += (G - V[s]) / N[s] # ສະເລ່ຍຜົນຕອບແທນຈິງທັງເກມ
return V
print("ຄ່າຈິງ :", np.round(np.arange(1, 6) / 6, 3))
print("TD(0) :", np.round(td0()[1:6], 3))
print("MC :", np.round(monte_carlo()[1:6], 3))Output
ຄ່າຈິງ : [0.167 0.333 0.5 0.667 0.833] TD(0) : [0.183 0.34 0.489 0.657 0.817] MC : [0.161 0.327 0.501 0.666 0.841]
- #DeepRL
- #ReinforcementLearning
- #PythonສຳລັບຄົນLaos
- #AI
- #ບອກຕໍ່ຄວາມຮູ້