Lặp giá trị (Value Iteration)

Lặp giá trị giải một quá trình quyết định Markov: nó tìm V(s), tổng phần thưởng chiết khấu tốt nhất có thể thu được khi bắt đầu từ trạng thái s.

Ở đây các bước chuyển là tất định. Ở trạng thái s, hành động a cho phần thưởng rewards[s][a] và chuyển sang trạng thái next_states[s][a], trong đó -1 nghĩa là tập kết thúc. Bắt đầu với V(s) = 0 cho mọi trạng thái, rồi lặp iterations lần, tính mọi giá trị mới từ lượt quét trước:

V_new(s) = max theo a của ( rewards[s][a] + gamma × V(next_states[s][a]) )

trong đó số hạng gamma × V bằng 0 khi trạng thái tiếp theo là -1.

Hãy viết value_iteration(next_states, rewards, gamma, iterations).

Đầu vào

next_states: Với mỗi trạng thái, trạng thái tiếp theo của từng hành động (-1 kết thúc tập). Các trạng thái có thể có số hành động khác nhau.

rewards: Phần thưởng của từng hành động, cùng hình dạng với next_states.

gamma: Hệ số chiết khấu.

iterations: Số lượt quét.

Đầu ra

Trả về V sau lượt quét cuối cùng, mỗi trạng thái một giá trị.

Ràng buộc

1 ≤ số trạng thái ≤ 200, 1 ≤ số hành động mỗi trạng thái ≤ 10, 0 ≤ iterations ≤ 1.000

-100 ≤ mỗi phần thưởng ≤ 100, 0 ≤ gamma ≤ 1

Ví dụ

Đầu vào:
gamma = 0.9
rewards = [
    [0.0, 0.0],
    [0.0, 0.0],
    [10.0]
]
iterations = 3
next_states = [
    [0, 1],
    [0, 2],
    [-1]
]

Kết quả mong đợi:
expected = [8.1, 9.0, 10.0]

Đầu vào:
double gamma = 0.9;
std::vector<std::vector<double>> rewards = {
    {0.0, 0.0},
    {0.0, 0.0},
    {10.0}
};
long long iterations = 3;
std::vector<std::vector<long long>> next_states = {
    {0, 1},
    {0, 2},
    {-1}
};

Kết quả mong đợi:
std::vector<double> expected = {8.1, 9.0, 10.0};

Đầu vào:
double gamma = 0.9;
double[][] rewards = new double[][] {
    new double[] {0.0, 0.0},
    new double[] {0.0, 0.0},
    new double[] {10.0}
};
long iterations = 3;
long[][] next_states = new long[][] {
    new long[] {0, 1},
    new long[] {0, 2},
    new long[] {-1}
};

Kết quả mong đợi:
double[] expected = new double[] {8.1, 9.0, 10.0};

Đầu vào:
gamma = 0.0
rewards = [
    [1.0, 2.0],
    [3.0, 0.0]
]
iterations = 5
next_states = [
    [1, 0],
    [0, 1]
]

Kết quả mong đợi:
expected = [2.0, 3.0]

Đầu vào:
double gamma = 0.0;
std::vector<std::vector<double>> rewards = {
    {1.0, 2.0},
    {3.0, 0.0}
};
long long iterations = 5;
std::vector<std::vector<long long>> next_states = {
    {1, 0},
    {0, 1}
};

Kết quả mong đợi:
std::vector<double> expected = {2.0, 3.0};

Đầu vào:
double gamma = 0.0;
double[][] rewards = new double[][] {
    new double[] {1.0, 2.0},
    new double[] {3.0, 0.0}
};
long iterations = 5;
long[][] next_states = new long[][] {
    new long[] {1, 0},
    new long[] {0, 1}
};

Kết quả mong đợi:
double[] expected = new double[] {2.0, 3.0};

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.

• Sutton and Barto, Reinforcement Learning: An Introduction (2nd edition)
• UC Berkeley CS188, Introduction to Artificial Intelligence