Department : Forsetry
Student : M10912004
Name : De-Kai Kao (高得愷)
## Introduction

強化學習(Reinforcement Learning, RL)是一種互動式的學習過程，通過觀察環境、進行測試和獲取回饋。這種方法的目標是使機器學習者（或稱為智能代理）通過與環境的互動，進行試驗和錯誤，以最大化預定義的獎勵或目標。

強化學習的核心概念是「獎勵信號」，它是對機器學習者行為的評價。當機器學習者採取正確的行動時，它將獲得正向的獎勵；相反，當它採取不正確的行動時，它將獲得負向的獎勵或懲罰。通過根據這些獎勵信號調整自身行為，機器學習者可以逐漸優化其策略，從而實現更好的性能，其中重要概念是價值函數（value function），它用於評估代理人(agent)在特定狀態下的長期回報。價值函數可以幫助判斷哪些行動是最有價值的，從而指導其策略的改進。

## MDP
馬可夫決策過程(Markov Decision Process)是一種數學框架，用於描述具有隨機性的決策問題。它包括狀態(states)、行動(actions)、轉移函數(transition function)、獎勵函數(reward function)和折扣因子(discount factor)等元素。MDP假設系統的演變遵循馬可夫性質，即當前狀態包含了過去狀態的所有必要資訊。

* 狀態(states)：狀態是在強化學習中描述問題環境的特定情況或配置。例如遊戲中的棋盤配置、機器人的位置和姿態，或者股市的市場狀態等。狀態在強化學習中用於表示代理人的知識基礎。

* 行動(actions)：行動代表代理人在特定狀態下可以選擇的可執行操作或決策。行動的選擇取決於當前的狀態，並且會影響代理人的後續狀態轉換和獲得的獎勵。行動可以是離散的（例如向左或向右移動）或連續的（例如控制機器人的速度和方向）。

* 轉移函數(transition function)：轉移函數定義了從一個狀態到另一個狀態的概率轉移。它描述了在特定狀態下，代理人選擇某個行動後，下一個狀態的可能性。轉移函數可以是明確定義的（例如在棋盤遊戲中的合法移動）或是根據隨機性和不確定性進行建模。

* 獎勵函數(reward function)：獎勵函數對代理人的行動進行評價，它定義了在特定狀態下代理人獲得的即時獎勵。獎勵可以是正向的(鼓勵代理人執行正確的行動)、負向的(懲罰代理人執行不正確的行動)或零(中性)的。獎勵函數是指導代理人學習過程中的關鍵元素，代理人的目標是通過最大化長期獎勵來選擇最佳的行動策略。

* 折扣因子(discount factor)：折扣因子是一個介於0和1之間的參數，用於平衡即時獎勵和未來回報的重要性。它表示代理人對未來獎勵的降低程度，即代理人更傾向於獲得即時獎勵，而對於遠期獎勵進行折扣。折扣因子使強化學習考慮到未來回報的重要性，並影響價值函數的計算和策略的形成。較小的折扣因子會導致更重視即時獎勵，而較大的折扣因子則更重視未來回報。

* 視野範圍(Horizon)：在強化學習中是指在一個學習問題中設定的時間範圍或評估的時間窗口。它代表了強化學習算法在每個時間步長上進行學習和決策的範圍。其長度可以是固定的，也可以是不固定的。在固定的範圍中，強化學習算法在每個時間步長上進行學習和行動選擇，直到達到預設的時間範圍。這種情況下，代理人需要在有限的時間內學會盡可能優化策略以獲得更好的回報。在不固定的情況下，強化學習算法可能沒有明確的終止時間，而是根據環境中的結束條件或其他停止條件來決定學習和決策的終止。範圍的設定會影響強化學習算法的行為和策略的形成。範圍較短可能會導致更注重即時獎勵，而較長的範圍則更注重長期回報和策略的穩定性。在設計強化學習問題時，長度需要根據問題的特性和需求進行適當的設置。

## Bellman Equation

貝爾曼方程(Bellman Equation)是動態規劃和強化學習中的重要方程，用於描述狀態值函數和行動值函數之間的關係。在馬可夫決策過程(MDP)中，最優值函數(Optimal Value Function)表示在每個狀態下執行最優策略所能達到的最大期望回報。貝爾曼方程提供了最優值函數的遞迴計算方式，它是根據最佳子結構性質而推導出的。

貝爾曼方程可以表示為以下形式：
$$
V_{\pi}(s)=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]
$$

* $s$ 狀態
* $s'$ 下一個狀態
* $a$ 動作
* $r$ 回報
* $\gamma$ 是折扣因子，表示未來回報的重要程度。
* $V_{\pi}(s)$ 是最優值函數，表示在狀態 $s$ 下執行最優策略所能達到的最大期望回報。
* $\sum_{a} \pi(a|s)$ 表示在狀態 $s$ 下，根據策的分佈選擇行動 $a$。

* $\sum_{s',r}p(s',r|s,a)$ 表示在狀態 $s$ 的情況下，根據選擇的行動 $a$，經過轉移函數 $p$ 從狀態 $s$ 轉移到下一個狀態 $s'$，同時獲得即時回報 $r$ 的機率分佈。

* $[r+\gamma v_\pi(s')]$ 表示在從狀態 $s$ 選擇行動 $a$ 後，獲得即時回報 $r$，然後根據策略 $\pi$ 在下一個狀態 $s'$ 的值 $v_\pi(s')$。$r+\gamma v_\pi(s')$ 是一個即時回報和折扣後的未來狀態值的線性組合，其中 $\gamma$ 是折扣因子，用於平衡即時回報和未來回報的重要性。

## Practice

* Actions slow Probability

| S' \ S | fallen | standing | moving |
| -------- | ------ | -------- | ------ |
| fallen | 0.6 | 0 | 0 |
| standing | 0.4 | 0 | 0 |
| moving | 0 | 1 | 1 |

* Actions slow Reward

| S' \ S | fallen | standing | moving |
| -------- | ------ | -------- | ------ |
| fallen | -1 | 0 | 0 |
| standing | 1 | 0 | 0 |
| moving | 0 | 1 | 1 |

* Actions fast Probability

| S' \ S | fallen | standing | moving |
|:--------:| ------ | -------- | ------ |
| fallen | 0 | 0.4 | 0.2 |
| standing | 0 | 0 | 0 |
| moving | 0 | 0.6 | 0.8 |

* Actions fast Reward

| S' \ S | fallen | standing | moving |
| -------- | ------ | -------- | ------ |
| fallen | 0 | -1 | -1 |
| standing | 0 | 0 | 0 |
| moving | 0 | 2 | 2 |

* State value Iteration method
$$
V_{k}=\mathop{max}_a\{R(s|a)+\gamma\sum_{s'}p(s,a,s')V_{k-1}(s')\}
$$
* $V_k$表示在第k次迭代中的狀態值函數。
* $R(s|a)$表示在狀態 $s$ 下執行行動a所得到的即時回報，
* $p(s,a,s')$表示在狀態 $s$ 下執行行動a後，轉移到下一狀態 $s'$ 的機率，
* $\gamma$ 是折扣因子（0 ≤ $\gamma$ ≤ 1），
* $V_{k-1}(s')$ 表示在第 $k-1$ 次迭代中的狀態值函數中狀態 $s'$ 的值。

方程式描述了狀態值函數之間的遞迴關係。對於每個狀態 $s$ ，我們需要在所有可能的行動 $a$ 中選擇能夠使得回報最大化的行動。我們使用 $\mathop{max}_a$ 表示選擇最大化回報的行動。

在方程式的右側，R(s|a)表示在狀態s下執行行動a所得到的即時回報。 $\gamma\sum_{s'}p(s,a,s')V_{k-1}(s')$ 表示在狀態 $s$ 下執行行動 $a$ 後，轉移到所有可能的下一狀態 $s'$ 的機率加權和。這部分表示了未來的累積回報，由折扣因子 $\gamma$ 控制未來回報的重要程度，並使用第 $k-1$ 次迭代的狀態值函數 $V_{k-1}(s')$ 來計算。

整個方程式的目的是找到使得狀態值函數最大化的值，即在每個狀態 $s$ 下選擇能夠最大化回報的行動，以最大化預期累積回報。通過多次迭代計算，狀態值函數 $V_k$ 會逐漸收斂到最優的狀態值函數，從而找到最優策略。
* k=1
$$
V_1=\mathop{max}_a\{R(s,slow),R(s,fast)\}\\=\mathop{max}_a\{\mathop{\begin{bmatrix} -0.2 \\ 1 \\ 1 \\\end{bmatrix}}_{slow}, \mathop{\begin{bmatrix} 0 \\ 0.8 \\ 1.4 \\\end{bmatrix}}_{fast}\}={\begin{bmatrix} 0\ \\ 1 \\ 1.4 \\\end{bmatrix}}\Rightarrow {\begin{bmatrix} Fallen-fast\ \\ Standing-slow \\ Moving-fast \\\end{bmatrix}}
$$

* k=2
$$
V_2=\mathop{max}_a\{R(:,1)+P(s,slow,s')V_1(s'),R(:,2)+P(s,fast,s')V_1(s')\}\\=\mathop{max}_a\{\mathop{\begin{bmatrix} -0.2 \\ 1 \\ 1 \\\end{bmatrix}}_{slow}+\mathop{\begin{bmatrix} 0.6 \quad0.4\quad0 \\ 0\quad0\quad1 \\ 0\quad0\quad1 \\\end{bmatrix}}^{P(s,slow,s')}\mathop{\begin{bmatrix} 0 \\ 1 \\ 1.4 \\\end{bmatrix}}^{V_1(s')}, \mathop{\begin{bmatrix} 0 \\ 0.8 \\ 1.4 \\\end{bmatrix}}_{fast}+\mathop{\begin{bmatrix} 0 \quad0\quad0 \\ 0.4\quad0\quad0.6 \\ 0.2\quad0\quad0.8 \\\end{bmatrix}}^{P(s,fast,s')}\mathop{\begin{bmatrix} 0 \\ 1 \\ 1.4 \\\end{bmatrix}}^{V_1(s')}\}\\=\mathop{max}_a\{{\begin{bmatrix} 0.2\ \\ 2.4 \\ 2.4 \\\end{bmatrix}},{\begin{bmatrix} 0\ \\ 1.64 \\ 2.52 \\\end{bmatrix}}\}=\mathop{\begin{bmatrix} 0.2\ \\ 2.4 \\ 2.52 \\\end{bmatrix}}^{V_2(s')}\Rightarrow {\begin{bmatrix} Fallen-slow\ \\ Standing-slow \\ Moving-fast \\\end{bmatrix}}
$$

* k=3
$$
V_3=\mathop{max}_a\{R(:,1)+P(s,slow,s')V_2(s'),R(:,2)+P(s,fast,s')V_2(s')\}\\=\mathop{max}_a\{\mathop{\begin{bmatrix} -0.2 \\ 1 \\ 1 \\\end{bmatrix}}_{slow}+\mathop{\begin{bmatrix} 0.6 \quad0.4\quad0 \\ 0\quad0\quad1 \\ 0\quad0\quad1 \\\end{bmatrix}}^{P(s,slow,s')}\mathop{\begin{bmatrix} 0.2\ \\ 2.4 \\ 2.52 \\\end{bmatrix}}^{V_2(s')}, \mathop{\begin{bmatrix} 0 \\ 0.8 \\ 1.4 \\\end{bmatrix}}_{fast}+\mathop{\begin{bmatrix} 0 \quad0\quad0 \\ 0.4\quad0\quad0.6 \\ 0.2\quad0\quad0.8 \\\end{bmatrix}}^{P(s,fast,s')}\mathop{\begin{bmatrix} 0.2\ \\ 2.4 \\ 2.52\\\end{bmatrix}}^{V_2(s')}\}\\=\mathop{max}_a\{{\begin{bmatrix} 0.88\ \\ 3.52 \\ 3.52\\\end{bmatrix}},{\begin{bmatrix} 0\ \\ 2.392 \\ 3.456 \\\end{bmatrix}}\}=\mathop{\begin{bmatrix} 0.88\ \\ 3.52 \\ 3.52 \\\end{bmatrix}}^{V_3(s')}\Rightarrow {\begin{bmatrix} Fallen-slow\ \\ Standing-slow \\ Moving-slow \\\end{bmatrix}}
$$

* k=4
$$
V_4=\mathop{max}_a\{R(:,1)+P(s,slow,s')V_3(s'),R(:,2)+P(s,fast,s')V_3(s')\}\\=\mathop{max}_a\{\mathop{\begin{bmatrix} -0.2 \\ 1 \\ 1 \\\end{bmatrix}}_{slow}+\mathop{\begin{bmatrix} 0.6 \quad0.4\quad0 \\ 0\quad0\quad1 \\ 0\quad0\quad1 \\\end{bmatrix}}^{P(s,slow,s')}\mathop{\begin{bmatrix} 0.88\ \\ 3.52 \\ 3.52 \\\end{bmatrix}}^{V_3(s')}, \mathop{\begin{bmatrix} 0 \\ 0.8 \\ 1.4 \\\end{bmatrix}}_{fast}+\mathop{\begin{bmatrix} 0 \quad0\quad0 \\ 0.4\quad0\quad0.6 \\ 0.2\quad0\quad0.8 \\\end{bmatrix}}^{P(s,fast,s')}\mathop{\begin{bmatrix} 0.88\ \\ 3.52 \\ 3.52 \\\end{bmatrix}}^{V_3(s')}\}\\=\mathop{max}_a\{{\begin{bmatrix} 1.736\ \\ 4.52 \\ 4.52 \\\end{bmatrix}},{\begin{bmatrix} 0\ \\ 3.264 \\ 4.392 \\\end{bmatrix}}\}=\mathop{\begin{bmatrix} 1.736\ \\ 4.52 \\ 4.52 \\\end{bmatrix}}^{V_4(s')}\Rightarrow {\begin{bmatrix} Fallen-slow\ \\ Standing-slow \\ Moving-slow \\\end{bmatrix}}
$$

* k=5
$$
V_5=\mathop{max}_a\{R(:,1)+P(s,slow,s')V_4(s'),R(:,2)+P(s,fast,s')V_4(s')\}\\=\mathop{max}_a\{\mathop{\begin{bmatrix} -0.2 \\ 1 \\ 1 \\\end{bmatrix}}_{slow}+\mathop{\begin{bmatrix} 0.6 \quad0.4\quad0 \\ 0\quad0\quad1 \\ 0\quad0\quad1 \\\end{bmatrix}}^{P(s,slow,s')}\mathop{\begin{bmatrix} 1.736\ \\ 4.52 \\ 4.52 \\\end{bmatrix}}^{V_4(s')}, \mathop{\begin{bmatrix} 0 \\ 0.8 \\ 1.4 \\\end{bmatrix}}_{fast}+\mathop{\begin{bmatrix} 0 \quad0\quad0 \\ 0.4\quad0\quad0.6 \\ 0.2\quad0\quad0.8 \\\end{bmatrix}}^{P(s,fast,s')}\mathop{\begin{bmatrix} 1.736\ \\ 4.52 \\ 4.52 \\\end{bmatrix}}^{V_4(s')}\}\\=\mathop{max}_a\{{\begin{bmatrix} 2.6496\\ 5.52 \\ 5.52 \\\end{bmatrix}},{\begin{bmatrix} 0 \\ 4.2056 \\ 5.3632 \\\end{bmatrix}}\}=\mathop{\begin{bmatrix} 2.6496\ \\ 5.392 \\ 5.392 \\\end{bmatrix}}^{V_5(s')}\Rightarrow {\begin{bmatrix} Fallen-slow\ \\ Standing-slow \\ Moving-slow \\\end{bmatrix}}
$$

## Python

import numpy as np

# 定義狀態和行動
states = ['standing', 'moving', 'fallen']
actions = ['move fast', 'move slow']

# 定義行動和狀態轉移的機率和回報
actions_prob = {
    'move fast': {
        'standing': {'standing': 0, 'moving': 0.6, 'fallen': 0.4},
        'moving': {'standing': 0, 'moving': 0.8, 'fallen': 0.2},
        'fallen': {'standing': 0, 'moving': 0, 'fallen': 0}
    },
    'move slow': {
        'standing': {'standing': 0, 'moving': 1, 'fallen': 0},
        'moving': {'standing': 0, 'moving': 1, 'fallen': 0},
        'fallen': {'standing': 0.4, 'moving': 0, 'fallen': 0.6}
    }
}

actions_reward = {
    'move fast': {
        'standing': {'standing': 0, 'moving': 2, 'fallen': -1},
        'moving': {'standing': 0, 'moving': 2, 'fallen': -1},
        'fallen': {'standing': 0, 'moving': 0, 'fallen': 0}
    },
    'move slow': {
        'standing': {'standing': 0, 'moving': 1, 'fallen': 0},
        'moving': {'standing': 0, 'moving': 1, 'fallen': 0},
        'fallen': {'standing': 1, 'moving': 0, 'fallen': -1}
    }
}

# 初始化狀態值函數
V = {
    'standing': 0,
    'moving': 0,
    'fallen': 0
}

# 貝爾曼方程式迭代計算
gamma = 1
num_iterations = 5


for _ in range(num_iterations):
    new_V = {}
    for state in states:
        values = []
        for action in actions:
            action_prob = actions_prob[action][state]
            action_reward = actions_reward[action][state]
            value = 0
            for next_state in states:
                value += action_prob[next_state] * (action_reward[next_state] \
                + gamma * V[next_state])
            values.append(value)
        print(actions[values.index(max(values))])
        new_V[state] = max(values)
    V = new_V
    print('k={}---------'.format(_+1))

# 輸出結果
for state in states:
    print(f"State: {state}, Value: {V[state]}")

- Result:

move slow
move fast
move fast
k=1---------
move slow
move fast
move slow
k=2---------
move slow
move slow
move slow
k=3---------
move slow
move slow
move slow
k=4---------
move slow
move slow
move slow
k=5---------
State: standing, Value: 5.5200000000000005
State: moving, Value: 5.5200000000000005
State: fallen, Value: 2.6496000000000004

* 可以由狀態值迭代函數計算出該機器人在 k=3 時開始收斂，無論在任何狀態都不會有除了 move slow 之外的動作。

## Conclusion

透過這次實作模擬機器人的狀態值函數，了解貝爾曼方程的應用和意義。該方程式表示狀態值函數之間的遞迴關係，將當前的狀態值與未來可能的狀態值相結合，選擇最優的行動。經過每次迭代中，根據行動機率和回報，計算出每個狀態的預期回報，並不斷更新狀態值函數，使其越接近最優值。

實作中用Python編寫了相應的程式碼，並根據講義提供的數據完成了機器人的狀態值函數計算，經過多次迭代得到了每個狀態的最大值，在不同狀態下採取不同行動的預期回報。此方式可以應用於各種強化學習問題，並找到最佳的策略。