Đề 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.
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.