1 of 19

Machine Learning HW5

MLTAs

ntueemlta2025@gmail.com

2 of 19

Links

3 of 19

Outline

  • HW5 Intro - Knight and Pawn
    • Tasks Description
  • Prerequisites
    • Soft update
    • ε-greedy algorithm
    • Upper Confidence Bound (UCB)
  • Regulations & Grading

4 of 19

Knight and Pawn

5 of 19

Task Description

Catch the pawn with your knight as soon as possible

6 of 19

Task Description

Rule

  • Goal: catch the pawn with a knight
  • Board setting: a standard 8*8 chess board with 8 fixed obstacles at the center of the board (d4,d5,e4,e5,c3,c6,f3,f6)
  • Initialization: a pawn and a knight at two random different positions (not on the obstacles)
  • In each round, the RL agent moves the knight according to the chess rules and should not move onto the obstacles. Then, the pawn moves downward one grid with a fixed probability. Catch the pawn before 50 rounds.

7 of 19

Task Description

Reinforcement Learning formulation

  • Finite-state MDP (tabular method)
    • State : {position of the knight} ✕ {position of the pawn} → total 64*64 states
    • Action : all legal movements of the knight → At most 8 possible actions
    • Transition : randomness from the pawn
    • Reward : Define your own reward.

(Default : 1 if the knight catches the pawn; -0.001 otherwise)

    • Discount factor : Define your own discount factor (Default : 1, no discount)

(But the evaluation is related to how early you catch the pawn.)

  • Learning Algorithm : Value iteration
    • Update the value function.

​

8 of 19

Prerequisites

9 of 19

Recap

​

​

​

​

​

How about V𝛑(s)?

Please express V𝛑(s) in terms of V𝛑 in your report.

​

​

10 of 19

Soft Update

In practice, assume your agent took action a in state s and get into state s’,

the updated value is directly updated into

V𝛑(s) ← r(s, a) + 𝛾V𝛑(s’),

which is called the hard update. On the other hand, soft update is a technique used to gradually update the parameters of a target (to be updated) network or value function towards the parameters of a source (computed) network or value function. It ensures smoother learning and avoids instability, particularly in environments with high variance or stochasticity. That is

V𝛑(s) ← 𝛕 · (r(s, a) + 𝛾V𝛑(s’)) + (1-𝛕) · V𝛑(s).

11 of 19

ε-greedy algorithm

The epsilon-greedy algorithm balances exploration and exploitation by choosing a random action with probability 𝜖 and the action with the highest estimated value with probability 1−𝜖. That is,

​

​

​

where r ~ Uniform(0,1) and S' is reached from S by a.

12 of 19

Upper Confidence Bound (UCB)

13 of 19

Regulations & Grading

14 of 19

Grading Policy - Deadline

  • Cool Deadline: 2025/12/19 23:59:59 (GMT+8)

15 of 19

Grading Criteria

Evaluation

  • Submit your V𝛑(s) table as an csv file
  • Total 200 test cases
    • 100 public cases
    • 100 private cases
    • These cases have different initial knight and pawn positions.
  • Score for each case :
    • TA will run a program with fixed random seed for fairness (transition)
    • If you catch the pawn in step i, the score for this case will be 100-i
    • If you failed to catch the pawn, the score for this case will be 0

16 of 19

Grading Criteria

  • Performance score - 4%
    • 超過public leaderboard simple baseline分數 (70.00) : 1%
    • 超過public leaderboard strong baseline分數 (93.46) : 1%
    • 超過private leaderboard simple baseline分數 (70.00) : 1%
    • 超過private leaderboard strong baseline分數 (93.25) : 1%
    • code template
  • Programming report - 2%
    • report template
  • Math problem - 6%
    • math problem
    • 若有和其他修課同學討論，請務必於題號前標明collaborator（含姓名、學號）

17 of 19

Cool Submissions

在Cool上分別繳交以下檔案：

  1. report.pdf
  2. math.pdf
  3. code.ipynb
  4. value_table.npy

18 of 19

Grading Policy - Others

  • Lateness
    • Cool 遲交第一天線性遞減至0.7，第二天線性遞減至0
    • 有特殊原因請找助教
  • Runtime Error
    • 當程式錯誤，造成助教無法順利執行，請在公告時間內寄信向助教說明，修好之後重新執行所得kaggle部分分數將x0.5。

19 of 19

學術倫理

  • Cheating
    • 抄code、抄report （含之前修課同學）
    • 開設kaggle多重分身帳號註冊competition
    • 教授與助教群保留請同學到辦公室解釋coding作業的權利

​