Quy Hoạch Động Lặp Giá Trị (Value Iteration) Cho Quá Trình Quyết Định Markov

Mục tiêu kiến thức

• Một quá trình quyết định Markov hữu hạn được định nghĩa bởi bộ langle S, A, P, R, γ rangle:
• S trạng thái, A hành động.
• Xác suất chuyển trạng thái P(s' | s, a): mảng kích thước (S, A, S).
• Phần thưởng kỳ vọng R(s, a): mảng kích thước (S, A).
• Hệ số chiết khấu γ ∈ [0, 1).
• **Phương trình tối ưu Bellman cho hàm giá trị V^*(s)**:

V_k+1(s) = max_{a ∈ A} [ R(s, a) + γ ∑_{s' ∈ S} P(s' | s, a) V_k(s') ]

• Thuật toán Value Iteration cập nhật lặp cho tới khi:

max_{s ∈ S} |V_k+1(s) - V_k(s)| < θ

• Chính sách tất định tối ưu tương ứng:

π^*(s) = argmax_{a ∈ A} [ R(s, a) + γ ∑_s' P(s' | s, a) V^*(s') ]

Yêu cầu

Viết hàm:

def value_iteration(
    transitions: np.ndarray,
    rewards: np.ndarray,
    gamma: float = 0.99,
    theta: float = 1e-6
) -> tuple[np.ndarray, np.ndarray]:
    pass

• Đầu vào:
• transitions: mảng float kích thước (S, A, S) thỏa mãn ∑_s' P(s'|s,a) = 1.
• rewards: mảng float kích thước (S, A).
• Đầu ra:
• V: vector (S,) chứa giá trị tối ưu của mỗi trạng thái.
• policy: vector số nguyên (S,) chứa chỉ số hành động tối ưu cho mỗi trạng thái (nếu hòa lấy chỉ số nhỏ nhất).

Ràng buộc

• Thời gian chạy tối đa: 2000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.