Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Value Iteration

Compute how valuable each state of a Markov decision process is by repeatedly applying the Bellman optimality update.

Bạn sẽ học được gì

  • Apply the Bellman optimality update
  • Compute state values sweep by sweep
  • Model decisions as states, actions and rewards

Đề bài

Xem bản dịch

Value iteration solves a Markov decision process: it finds V(s), the best total discounted reward you can collect starting from state s.

Here the transitions are deterministic. In state s, action a gives reward rewards[s][a] and moves to state next_states[s][a], where -1 means the episode ends. Start with V(s) = 0 for every state, then repeat iterations times, computing every new value from the previous sweep:

V_new(s) = max over a of ( rewards[s][a] + gamma × V(next_states[s][a]) )

where the gamma × V term is 0 when the next state is -1.

Implement value_iteration(next_states, rewards, gamma, iterations).

Input

next_states: For each state, the next state of each of its actions (-1 ends the episode). States may have different numbers of actions.

rewards: The reward of each action, with the same shape as next_states.

gamma: The discount factor.

iterations: The number of sweeps.

Output

Return V after the last sweep, one value per state.

Ràng buộc

1 ≤ states ≤ 200, 1 ≤ actions per state ≤ 10, 0 ≤ iterations ≤ 1,000

-100 ≤ each reward ≤ 100, 0 ≤ gamma ≤ 1

Ví dụ

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

Kết quả mong đợi:
expected = [8.1, 9.0, 10.0]
Đầu vào:
std::vector<std::vector<long long>> next_states = {
    {0, 1},
    {0, 2},
    {-1}
};
std::vector<std::vector<double>> rewards = {
    {0.0, 0.0},
    {0.0, 0.0},
    {10.0}
};
double gamma = 0.9;
long long iterations = 3;

Kết quả mong đợi:
std::vector<double> expected = {8.1, 9.0, 10.0};
Đầu vào:
long[][] next_states = new long[][] {
    new long[] {0, 1},
    new long[] {0, 2},
    new long[] {-1}
};
double[][] rewards = new double[][] {
    new double[] {0.0, 0.0},
    new double[] {0.0, 0.0},
    new double[] {10.0}
};
double gamma = 0.9;
long iterations = 3;

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

Giải thích

Sweep 1: only state 2 can collect a reward, V = [0, 0, 10]. Sweep 2: state 1 moves right to it, 0.9 × 10 = 9, V = [0, 9, 10]. Sweep 3: state 0 gets 0.9 × 9 = 8.1. Result: [8.1, 9, 10].

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

Kết quả mong đợi:
expected = [2.0, 3.0]
Đầu vào:
std::vector<std::vector<long long>> next_states = {
    {1, 0},
    {0, 1}
};
std::vector<std::vector<double>> rewards = {
    {1.0, 2.0},
    {3.0, 0.0}
};
double gamma = 0.0;
long long iterations = 5;

Kết quả mong đợi:
std::vector<double> expected = {2.0, 3.0};
Đầu vào:
long[][] next_states = new long[][] {
    new long[] {1, 0},
    new long[] {0, 1}
};
double[][] rewards = new double[][] {
    new double[] {1.0, 2.0},
    new double[] {3.0, 0.0}
};
double gamma = 0.0;
long iterations = 5;

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

Giải thích

With gamma = 0 the future does not count, so each state's value is just its best immediate reward: [2, 3].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Every sweep uses only the values from the previous sweep, not updates made earlier in the same pass.

Gợi ý 2

For each state, compare all actions by combining immediate reward with the discounted value of the next state.

Gợi ý 3

Handle terminal actions carefully: they contribute only their immediate reward when the next state is missing.

Độ phức tạp mong đợi

O(iterations * total_actions) time, O(states) extra space

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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.