Bài tập Reinforcement learning

Bài 1Return

Robot đi một episode và nhận phần thưởng $r_0, r_1, \dots, r_{T-1}$ . Một bước ở xa đích có giá trị bao nhiêu? Return của bước $t$ cộng mọi phần thưởng từ bước ấy về sau, phần thưởng càng xa càng bị chiết khấu:

G_t=r_t+\gamma r_{t+1}+\gamma^2 r_{t+2}+\cdots=r_t+\gamma G_{t+1},\qquad G_T=0.

Hãy tính $G_t$ cho mọi $t$ .

Dữ liệu vào

Một đối tượng JSON gồm rewards và gamma.

Kết quả

Một đối tượng JSON gồm returns (dãy $G_0..G_{T-1}$ ) và G0.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{"rewards": [-1, -1, -1, 10], "gamma": 0.9}

Output mẫu

{"returns": [4.58, 6.2, 8.0, 10.0], "G0": 4.58}

Bài 2Một bước Bellman

Đề bài Dữ liệu

Phương trình Bellman tính việc xa bằng việc gần: giá trị của một hành động là phần thưởng ngay cộng giá trị (chiết khấu) của trạng thái tới.

Cho mô hình môi trường P: P[s][a] là danh sách các khả năng $[p, s', r]$ (xác suất, trạng thái tới, phần thưởng) khi làm $a$ ở $s$ ; ước lượng giá trị hiện tại V; hệ số $\gamma$ ; tập trạng thái kết thúc terminal (giá trị luôn coi là $0$ ).

Với mỗi trạng thái $s$ trong P (theo thứ tự chuỗi) và mỗi hành động $a$ :

Q(s,a)=\sum p\cdot\big(r+\gamma\,V(s')\big),

với $V(s')=0$ nếu $s'$ là trạng thái kết thúc. Hành động tham lam là hành động có $Q$ lớn nhất (bằng nhau thì tên nhỏ hơn), và giá trị mới của $s$ là $Q$ ấy.

Dữ liệu vào

Một đối tượng JSON gồm P, V, gamma và terminal.

Kết quả

Một đối tượng JSON gồm states: từ trạng thái tới {"Q", "greedy", "new_V"}.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "P": {
    "s0": {
      "right": [[0.5, "goal", 0], [0.5, "s0", 0]],
      "stay": [[1.0, "s1", -1]]
    },
    "s1": {
      "left": [[1.0, "goal", 1]],
      "right": [[0.8, "s0", 1], [0.2, "goal", 1]]
    }
  },
  "V": {"s0": 7, "s1": -5, "goal": -2},
  "gamma": 0.5,
  "terminal": ["goal"]
}

Output mẫu

{
  "states": {
    "s0": {
      "Q": {"right": 1.75, "stay": -3.5},
      "greedy": "right",
      "new_V": 1.75
    },
    "s1": {"Q": {"left": 1.0, "right": 3.8}, "greedy": "right", "new_V": 3.8}
  }
}

Bài 3Policy gradient

Đề bài Dữ liệu

Policy gradient học thẳng xác suất chọn hành động. Bài này làm trên bài toán một bước: chọn một trong $K$ hành động, nhận phần thưởng, kết thúc.

Policy là softmax của tham số $\theta$ : $\pi_k=e^{\theta_k}/\sum_j e^{\theta_j}$ .

Có $n$ mẫu, mỗi mẫu là (hành động $a$ , phần thưởng $r$ ). Baseline $b$ là trung bình phần thưởng của các mẫu nếu baseline là true, ngược lại $b=0$ .
Ước lượng gradient (REINFORCE): $g_k=\frac1n\sum_{\text{mẫu}}(r-b)\big([k=a]-\pi_k\big)$ . (Đây là đạo hàm của $\log\pi_a$ theo $\theta_k$ , nhân $r-b$ .)
Cập nhật một bước: $\theta\leftarrow\theta+\text{lr}\cdot g$ .

Dữ liệu vào

Một đối tượng JSON gồm theta, samples (mỗi mẫu là {"action", "reward"}), baseline và lr.

Kết quả

Một đối tượng JSON gồm policy, baseline, gradient và new_theta.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "theta": [0.0, 0.0, 0.0],
  "samples": [
    {"action": 0, "reward": 1},
    {"action": 1, "reward": 3},
    {"action": 0, "reward": 1}
  ],
  "baseline": true,
  "lr": 0.5
}

Output mẫu

{
  "policy": [0.3333333333333333, 0.3333333333333333, 0.3333333333333333],
  "baseline": 1.6666666666666667,
  "gradient": [-0.4444444444444445, 0.4444444444444444, 1.850371707708594e-17],
  "new_theta": [-0.22222222222222224, 0.2222222222222222, 9.25185853854297e-18]
}

Bài 4Q-learning

Đề bài Dữ liệu

Q-learning không cần biết mô hình môi trường: nó học từ từng bộ trải nghiệm $(s, a, r, s')$ , tức ở trạng thái $s$ làm $a$ , nhận $r$ và tới $s'$ . Bài này chạy đúng chuỗi cập nhật ấy.

Mọi $Q(s,a)$ ban đầu bằng $0$ . Với mỗi bộ trải nghiệm theo thứ tự:

Q(s,a)\leftarrow(1-\alpha)\,Q(s,a)+\alpha\Big(r+\gamma\max_{a'}Q(s',a')\Big),

trong đó nếu $s'$ là trạng thái kết thúc (trong terminal) thì phần $\max_{a'}Q(s',a')$ coi là $0$ . Mỗi bước dùng giá trị $Q$ hiện tại (đã gồm các cập nhật trước).

Báo giá trị mới sau từng cập nhật, bảng $Q$ cuối cùng, và hành động tham lam ở mỗi trạng thái không kết thúc (bằng nhau thì hành động đứng trước trong actions).

Dữ liệu vào

Một đối tượng JSON gồm states, actions, gamma, alpha, terminal và experience (mỗi bộ là $[s, a, r, s']$ ).

Kết quả

Một đối tượng JSON gồm updates (mỗi cập nhật là {"state", "action", "value"}), Q (từ trạng thái tới từ hành động tới giá trị) và greedy.

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "states": ["A", "B", "C", "D"],
  "actions": ["Move", "Stay"],
  "gamma": 0.9,
  "alpha": 1.0,
  "terminal": [],
  "experience": [
    ["A", "Move", 0, "B"],
    ["B", "Move", 0, "C"],
    ["C", "Move", 1, "A"],
    ["A", "Move", 0, "B"],
    ["B", "Move", 0, "C"],
    ["A", "Move", 0, "B"],
    ["B", "Move", 0, "D"]
  ]
}

Output mẫu

{
  "updates": [
    {"state": "A", "action": "Move", "value": 0.0},
    {"state": "B", "action": "Move", "value": 0.0},
    {"state": "C", "action": "Move", "value": 1.0},
    {"state": "A", "action": "Move", "value": 0.0},
    {"state": "B", "action": "Move", "value": 0.9},
    {"state": "A", "action": "Move", "value": 0.81},
    {"state": "B", "action": "Move", "value": 0.0}
  ],
  "Q": {
    "A": {"Move": 0.81, "Stay": 0.0},
    "B": {"Move": 0.0, "Stay": 0.0},
    "C": {"Move": 1.0, "Stay": 0.0},
    "D": {"Move": 0.0, "Stay": 0.0}
  },
  "greedy": {"A": "Move", "B": "Move", "C": "Move", "D": "Move"}
}

Bài 5Value iteration

Đề bài Dữ liệu

Khi biết đầy đủ mô hình (xác suất chuyển trạng thái, phần thưởng), ta có thể lập kế hoạch mà không cần thử: value iteration. Bài này tính giá trị tối ưu theo từng horizon (số bước còn lại), và giá trị vô hạn bước của một policy cố định.

Phần thưởng gắn với trạng thái: ở trạng thái $s$ nhận $R(s)$ rồi mới chuyển. transitions[s][a] là phân phối trạng thái tới khi làm $a$ ở $s$ .

Horizon. $V_0(s)=0$ ; với $h=1..H$ :

Q_h(s,a)=R(s)+\gamma\sum_{s'}P(s'\mid s,a)\,V_{h-1}(s'),\qquad V_h(s)=\max_a Q_h(s,a).

Báo $V_h$ và các hành động tối ưu ở mỗi trạng thái (mọi hành động đạt giá trị lớn nhất, sai lệch dưới $10^{-9}$ , theo thứ tự trong actions). 2. Policy cố định. Với policy $\pi$ cho sẵn, giá trị vô hạn bước thỏa $V^\pi(s)=R(s)+\gamma\sum_{s'}P(s'\mid s,\pi(s))V^\pi(s')$ . Giải hệ phương trình tuyến tính ấy.

Dữ liệu vào

Một đối tượng JSON gồm states, actions, gamma ( $<1$ ), horizon, reward, transitions và policy.

Kết quả

Một đối tượng JSON gồm horizons (với mỗi $h$ là {"h", "V", "best_actions"}) và policy_value.

Giới hạn

Không quá $5$ trạng thái, $H\le4$ .

Chấm điểm

Có 20 test, mỗi test 5 điểm. Số thực được chấm với sai số khoảng $10^{-7}$ .

Ví dụ

Input mẫu

{
  "states": ["S0", "S1", "S2", "S3"],
  "actions": ["A", "B"],
  "gamma": 0.8,
  "horizon": 3,
  "reward": {"S0": 0, "S1": 10, "S2": 2, "S3": 1},
  "transitions": {
    "S0": {"A": {"S1": 0.1, "S3": 0.9}, "B": {"S2": 1.0}},
    "S1": {"A": {"S3": 1.0}, "B": {"S3": 1.0}},
    "S2": {"A": {"S0": 1.0}, "B": {"S2": 0.5, "S3": 0.5}},
    "S3": {"A": {"S3": 1.0}, "B": {"S3": 1.0}}
  },
  "policy": {"S0": "B", "S1": "A", "S2": "A", "S3": "A"}
}

Output mẫu

{
  "horizons": [
    {
      "h": 1,
      "V": {"S0": 0.0, "S1": 10.0, "S2": 2.0, "S3": 1.0},
      "best_actions": {
        "S0": ["A", "B"],
        "S1": ["A", "B"],
        "S2": ["A", "B"],
        "S3": ["A", "B"]
      }
    },
    {
      "h": 2,
      "V": {"S0": 1.6, "S1": 10.8, "S2": 3.2, "S3": 1.8},
      "best_actions": {"S0": ["B"], "S1": ["A", "B"], "S2": ["B"], "S3": ["A", "B"]}
    },
    {
      "h": 3,
      "V": {"S0": 2.56, "S1": 11.44, "S2": 4.0, "S3": 2.44},
      "best_actions": {"S0": ["B"], "S1": ["A", "B"], "S2": ["B"], "S3": ["A", "B"]}
    }
  ],
  "policy_value": {
    "S0": 4.4444444444444455,
    "S1": 14.0,
    "S2": 5.555555555555557,
    "S3": 5.000000000000001
  }
}