Dự đoán
Q-Learning: tại mỗi ngã tư (state), thử hành động (rẽ trái/phải/thẳng), nhận reward (nhanh = +, chậm = -). Dần dần xây dựng 'bản đồ giá trị' (Q-table): tại mỗi ngã tư, biết rẽ hướng nào có giá trị cao nhất.
Evaluating routing across providers.
AI Researcher
Thuật toán học tăng cường cơ bản học giá trị hành động tối ưu từ trải nghiệm
Q-Learning: tại mỗi ngã tư (state), thử hành động (rẽ trái/phải/thẳng), nhận reward (nhanh = +, chậm = -). Dần dần xây dựng 'bản đồ giá trị' (Q-table): tại mỗi ngã tư, biết rẽ hướng nào có giá trị cao nhất.
Sau nhiều lần thử, agent học được bản đồ giá trị (Q-table): tại mỗi ô, biết đi hướng nào có giá trị cao nhất. Q values lan ngược từ đích — ô gần đích có Q cao, ô xa hơn thì Q thấp dần. Agent đi theo gradient của Q values — giống nước chảy từ núi xuống thung lũng!
Đây là điểm khác biệt then chốt so với supervised learning: không ai dạy agent "đi đâu". Agent tự khám phá, tự chấm điểm, và tự xây bản đồ của riêng nó. Tín hiệu duy nhất là reward.
Epsilon decay: ban đầu explore nhiều (0.3-1.0) để khám phá, sau đó giảm dần (0.05-0.01) để khai thác kiến thức. ε = 0 nguy hiểm: môi trường thay đổi thì agent không adapt được. Giữ ε khoảng 0.01-0.05 là cân bằng tốt.
Một ô có Q = [2.0, 5.0, 1.5, 3.0] cho [Up, Right, Down, Left]. Action Right đưa agent vào ô có max Q' = 6, reward = -0.1. Với α = 0.5, γ = 0.9, Q(s, Right) mới là?
Áp dụng: Q ← Q + α·[r + γ·maxQ' − Q] = 5.0 + 0.5·(−0.1 + 5.4 − 5.0) = 5.0 + 0.5·0.3 = 5.15. Q dịch nhẹ về phía target. Lặp nhiều lần, Q hội tụ tới giá trị kỳ vọng thật sự.
Q-Learning là thuật toán RL học giá trị — "hành động a tại state s tốt đến đâu?" — từ trải nghiệm (off-policy, model-free). Khi state space quá lớn (hình ảnh, game), Q-table được thay bằng neural network — xem Deep Q-Network (DQN) . Một nhánh khác là học trực tiếp policy thay vì value function — xem Policy Gradient .
Phương trình Bellman tối ưu:
Quy tắc cập nhật Q-Learning:
Trong đó:
Điều kiện hội tụ: Q-Learning hội tụ tới với xác suất 1 nếu:
Thực tế: state lớn → cần xấp xỉ hàm (neural network), mất bảo đảm hội tụ nhưng thường vẫn work tốt.
import numpy as np
GRID = 5
N_ACTIONS = 4 # Up, Right, Down, Left
DELTAS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
WALLS = {(1, 1), (1, 3), (2, 1), (3, 2), (3, 3)}
TRAPS = {(2, 3)}
GOAL = (4, 4)
START = (0, 0)
def step(r: int, c: int, a: int) -> tuple[int, int, float, bool]:
dr, dc = DELTAS[a]
nr, nc = r + dr, c + dc
# Biên và tường
if not (0 <= nr < GRID and 0 <= nc < GRID) or (nr, nc) in WALLS:
nr, nc = r, c
# Reward
if (nr, nc) == GOAL:
return nr, nc, 10.0, True
if (nr, nc) in TRAPS:
return nr, nc, -5.0, False
return nr, nc, -0.1, False
def select_action(q: np.ndarray, r: int, c: int, eps: float) -> int:
if np.random.rand() < eps:
return np.random.randint(N_ACTIONS)
return int(np.argmax(q[r, c]))
def train(episodes: int = 1000) -> np.ndarray:
q = np.zeros((GRID, GRID, N_ACTIONS))
alpha, gamma = 0.3, 0.95
eps, eps_min, eps_decay = 0.4, 0.05, 0.995
for ep in range(episodes):
r, c = START
for _ in range(200): # giới hạn bước
a = select_action(q, r, c, eps)
nr, nc, reward, done = step(r, c, a)
# ── Bellman update ──
td_target = reward + gamma * q[nr, nc].max()
q[r, c, a] += alpha * (td_target - q[r, c, a])
r, c = nr, nc
if done:
break
eps = max(eps_min, eps * eps_decay)
return q
if __name__ == "__main__":
q_opt = train(episodes=2000)
# Chính sách tối ưu π(s) = argmax_a Q(s, a)
policy = q_opt.argmax(axis=-1)
print("Optimal policy (0=Up, 1=Right, 2=Down, 3=Left):")
print(policy)import numpy as np
# Double Q-Learning: dùng 2 bảng Q luân phiên để tránh max bias.
# Một bảng chọn action, bảng kia đánh giá → giảm overestimation.
def double_q_update(
qa: np.ndarray,
qb: np.ndarray,
s: tuple[int, int],
a: int,
r: float,
s_next: tuple[int, int],
alpha: float,
gamma: float,
) -> None:
if np.random.rand() < 0.5:
# Cập nhật Qa bằng đánh giá của Qb tại argmax theo Qa
best_a = int(np.argmax(qa[s_next]))
target = r + gamma * qb[s_next + (best_a,)]
qa[s + (a,)] += alpha * (target - qa[s + (a,)])
else:
best_a = int(np.argmax(qb[s_next]))
target = r + gamma * qa[s_next + (best_a,)]
qb[s + (a,)] += alpha * (target - qb[s + (a,)])
def policy_from_double_q(qa: np.ndarray, qb: np.ndarray) -> np.ndarray:
"""Chính sách dùng trung bình hai bảng."""
return ((qa + qb) / 2).argmax(axis=-1)Toán tử có tính chất: . Khi Q có nhiễu ước lượng (đương nhiên, do mẫu hữu hạn), max trên các ước lượng nhiễu sẽ luôn nghiêng về phía lớn — đẩy Q lên cao hơn giá trị thật. Càng nhiều action, bias càng nặng.
Double Q-Learning (van Hasselt 2010) tách đôi: một mạng chọn action, mạng khác đánh giá. Hai ước lượng độc lập hủy bớt bias. Double DQN áp dụng ý tưởng này cho deep RL.
Discount factor γ ∈ [0, 1) quyết định "tầm nhìn xa" của agent. γ = 0 → chỉ quan tâm reward ngay; γ → 1 → lên kế hoạch dài hạn. Ảnh hưởng thực tế:
Trong Atari, γ = 0.99 là chuẩn. Trong robotics dài hạn, người ta dùng γ = 0.995-0.999. Trò chơi cờ — γ có thể bằng 1.0 vì episode hữu hạn rõ ràng.
Markov Decision Process (MDP) là khung toán học của RL. Một MDP gồm 5 thành phần :
Agent muốn tìm chính sách tối ưu — hàm trả về action tốt nhất cho mỗi state — sao cho kỳ vọng tổng reward tương lai (có chiết khấu) là lớn nhất:
Hàm giá trị trạng thái và hàm giá trị hành động:
Liên hệ giữa hai hàm: . Chính sách tối ưu chọn argmax của Q: .
Hội tụ và lý thuyết: Theorem Watkins & Dayan (1992) chứng minh Q-Learning hội tụ tới với xác suất 1 trong MDP tabular, với điều kiện mọi cặp (s, a) được thăm vô hạn lần và learning rate thoả điều kiện Robbins-Monro. Trong thực tế với function approximation (DQN), mất bảo đảm hội tụ nhưng vẫn work nhờ experience replay và target network.
So sánh nhanh các họ RL:
Ứng dụng thực tế: