Một lần quét value iteration trên MDP nhỏ
Value iteration là thuật toán nền tảng của học tăng cường: lặp đi lặp lại phép gán
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, ai-markov-decision-process.
Nội dung đề bài
Mô tả bài toán
Value iteration là thuật toán nền tảng của học tăng cường: lặp đi lặp lại phép gán V(s) = max_a ( r(s, a) + gamma * sum_{s'} p(s' | s, a) * V(s') ). Một lần quét cập nhật đồng thời mọi trạng thái từ bảng V cũ, và đó chính là bước bạn phải viết.
Yêu cầu
Viết hàm value_iteration_sweep(values, rewards, transitions, gamma) trả về danh sách giá trị mới sau đúng một lần quét, dùng values cũ cho mọi trạng thái.
Quy ước nộp bài
Nộp hàm value_iteration_sweep trong solution.py. Hệ thống gọi hàm trực tiếp và so với sai số 1e-6; không đọc stdin và không in ra stdout.
Input
- values: giá trị hiện tại V(s), danh sách dài N.
- rewards: rewards[s][a] là phần thưởng tức thời (một số).
- transitions: transitions[s][a] là danh sách các cặp [xác suất, trạng thái kế].
- gamma: hệ số chiết khấu trong [0, 1].
Output
Danh sách dài N là V mới.
Ràng buộc
- gamma phải trong [0, 1]; nếu không, ném ValueError.
- Dùng values cũ cho mọi trạng thái (cập nhật đồng thời, không dùng giá trị vừa tính).
Ví dụ 1
Input
value_iteration_sweep(values=[0.0, 0.0], rewards=[[1, 0], [0, 2]], transitions=[[[[1.0, 1]], [[1.0, 0]]], [[[1.0, 0]], [[1.0, 1]]]], gamma=0.5)
Output
[1.0, 2.0]
Ví dụ 2
Input
value_iteration_sweep(values=[2.0, 2.0], rewards=[[1, 0], [0, 2]], transitions=[[[[1.0, 1]], [[1.0, 0]]], [[[1.0, 0]], [[1.0, 1]]]], gamma=0.5)
Output
[2.0, 3.0]
Giải thích
Với hai trạng thái, rewards = [[1, 0], [0, 2]], chuyển tiếp xác định (a = 0 đi sang trạng thái 1, a = 1 đi sang trạng thái 0), values = [2, 2] và gamma = 0.5: trạng thái 0 chọn 1 + 0.5 * 2 = 2, trạng thái 1 chọn 2 + 0.5 * 2 = 3, nên kết quả là [2.0, 3.0].
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
