Đề bài
Q-learning học xem mỗi hành động tốt đến đâu trong mỗi trạng thái, Q(s, a), chỉ từ trải nghiệm. Sau khi thực hiện hành động a ở trạng thái s, nhận reward và đến trạng thái s':
- target = reward, nếu tập (episode) đã kết thúc (
done= 1) - target = reward + gamma × max theo a' của Q(s', a'), ngược lại
- Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))
Bắt đầu với mọi giá trị Q bằng 0 và áp dụng các bước chuyển theo thứ tự.
Hãy viết q_learning(num_states, num_actions, transitions, alpha, gamma).
Đầu vào
num_states, num_actions: Kích thước bảng.
transitions: Mỗi bước một hàng [state, action, reward, next_state, done].
alpha: Tốc độ học.
gamma: Hệ số chiết khấu.
Đầu ra
Trả về bảng Q dưới dạng ma trận, mỗi hàng là một trạng thái và mỗi cột là một hành động.
Ràng buộc
1 ≤ num_states, num_actions ≤ 100, 0 ≤ số bước chuyển ≤ 10.000
-100 ≤ reward ≤ 100, done là 0 hoặc 1
0 < alpha ≤ 1, 0 ≤ gamma ≤ 1
Ví dụ
Đầu vào:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
Kết quả mong đợi:
expected = [
[0.0, 0.0],
[5.0, 0.0]
]Đầu vào:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{0, 1, 0, 1, 0},
{1, 0, 10, 0, 1}
};
Kết quả mong đợi:
std::vector<std::vector<double>> expected = {
{0.0, 0.0},
{5.0, 0.0}
};Đầu vào:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {0, 1, 0, 1, 0},
new long[] {1, 0, 10, 0, 1}
};
Kết quả mong đợi:
double[][] expected = new double[][] {
new double[] {0.0, 0.0},
new double[] {5.0, 0.0}
};Giải thích
Bước đầu chưa có phần thưởng: target = 0 + 0.9 × max(Q[1]) = 0, nên Q[0][1] vẫn là 0. Bước thứ hai kết thúc tập với phần thưởng 10: Q[1][0] = 0 + 0.5 × (10 - 0) = 5.
Đầu vào:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[1, 0, 10, 0, 1],
[0, 1, 0, 1, 0]
]
Kết quả mong đợi:
expected = [
[0.0, 2.25],
[5.0, 0.0]
]Đầu vào:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{1, 0, 10, 0, 1},
{0, 1, 0, 1, 0}
};
Kết quả mong đợi:
std::vector<std::vector<double>> expected = {
{0.0, 2.25},
{5.0, 0.0}
};Đầu vào:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {1, 0, 10, 0, 1},
new long[] {0, 1, 0, 1, 0}
};
Kết quả mong đợi:
double[][] expected = new double[][] {
new double[] {0.0, 2.25},
new double[] {5.0, 0.0}
};Giải thích
Cùng các bước nhưng theo thứ tự ngược lại. Q[1][0] thành 5 trước, nên bước từ trạng thái 0 giờ thấy giá trị đó: target = 0 + 0.9 × 5 = 4.5 và Q[0][1] = 0.5 × 4.5 = 2.25. Phần thưởng đã lan ngược lại một trạng thái.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Mỗi chuyển trạng thái chỉ cập nhật một ô bảng bằng giá trị hiện tại của nó và ước lượng tốt nhất từ trạng thái tiếp theo.
Gợi ý 2
Giữ bảng Q khởi tạo bằng 0, rồi xử lý các chuyển trạng thái theo thứ tự và cập nhật ngay sau mỗi bước.
Gợi ý 3
Nếu episode kết thúc thì không có giá trị tương lai để cộng thêm, và không dùng max của trạng thái kế tiếp.
Độ phức tạp mong đợi
thời gian O(T * A), bộ nhớ phụ O(S * A)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.