# Q-learning: Markov Decision Process + Reinforcement Learning
> * 馬爾可夫決策過程（Markov Decision Process，簡稱MDP）是一種用於描述序列決策問題的數學框架。它是強化學習中最常見的建模工具之一。以下是馬爾可夫決策過程的一些**基本概念**：
>
> 1. 狀態（State, 簡稱 S）: S 是一個有限集合，代表系統可能處於的各種情況。
> 這些情況可以是具體的、可觀察的特徵，也可以是系統的內部表示。在某一時間
> 點，系統處於某一狀態。
>
> 2. 動作空間（Action, 簡稱 A) : A 是動作的有限集合，動作的集合形成了主體
> 可以進行的所有可能決策。
>
> 3. 轉換概率（Transition Probability, P(s’| s, a)）: 描述在執行一
> 個動作後系統從一個狀態轉移到另一個狀態的概率。這一轉換通常以條件概率的
> 形式表示，即在給定當前狀態和執行的動作的情況下，系統轉移到下一狀態的概
> 率。
>
> 4. 獎勵函數（Reward, 簡稱 R(s) ) : 代表在某一狀態下執行某一動作後，系統
> 給予主體的即時回饋。獎勵可以是正面的、負面的或零，用於評估主體的動作。
>
> 5. 策略（Policy, 簡稱 π(s) ) : π 是從狀態到動作的映射，指定代理在每個狀
> 態下應該選擇的動作形式上表示為 π(a|s)，表示在狀態s下選擇動作a的概率。
>
> 6. 回報（Return）: G(t) 是代理在時間 t 開始後獲得的累積總獎勵常見的形式
> 是折扣回報（Discounted Return)，折扣回報的計算公式如下
> G(t) = R(t) + γ * R(t+1) + γ ^ 2 * R(t + 2) + ...
> = Σ(γ ^ k * R( t + k )), k = 0 到 ∞
> γ 是折扣因子，0≤γ≤1。它表示未來回饋的價值隨著時間的推移而遞減。
> 如果 γ 接近 1，則未來的回饋對當前回饋的影響就越小。
>
* 馬爾可夫決策過程的目標是找到一個策略，使得主體在整個時間序列中獲得最大的回饋。這涉及在狀態空間和動作空間中搜索最優的策略。強化學習算法，如值迭代、策略迭代、Q學習和深度強化學習方法，被用於解決MDP問題。

## practice

    題目：老鼠走迷宮

    介紹：這是一個簡單的迷宮問題，其中老鼠需要尋找通往迷宮出口的最佳路徑。迷宮是一個
         二維陣列，由不同的數字表示不同的區域：

            0 表示可走的路徑。
            1 表示牆壁，老鼠無法穿過。
            2 表示出口，老鼠需要找到這個點以成功通關。
            老鼠的初始位置固定在迷宮的左上角。

    使用者可以手動輸入迷宮的尺寸以及每個位置的屬性，包括牆壁和出口的位置。程式將模擬
    老鼠在迷宮中移動的過程，並使用Q學習算法來學習最佳行動策略。在每一回合中，老鼠會
    根據當前狀態選擇行動，然後根據行動的結果獲得獎勵。Q學習算法將這些獎勵用於更新老
    鼠對於每個狀態和行動的預期價值，從而使老鼠不斷改進其策略，直到找到最佳路徑達到
    出口。

## Code

### Step 1. 引入套件(numpy, matplotlib)

import numpy as np
import matplotlib.pyplot as plt

### Step 2. QLearningAgent

class QLearningAgent:
    #learning_rate：學習率，是一個介於 0 到 1 之間的數值，用於控制每次更新 Q 值時新資訊的影響程度。
    #discount_factor：折扣因子，是一個介於 0 到 1 之間的數值，用於表示未來回饋的折扣程度。這個值越大，越重視未來的回饋。
    #exploration_prob：探索機率，是一個介於 0 到 1 之間的數值，表示在選擇動作時進行探索的機率。如果隨機數小於 exploration_prob，則進行探索，否則進行利用。
    def __init__(self, num_states, num_actions, learning_rate=0.1, discount_factor=0.9, exploration_prob=0.1):
        self.num_states = num_states
        self.num_actions = num_actions
        self.learning_rate = learning_rate
        self.discount_factor = discount_factor
        self.exploration_prob = exploration_prob

        # Initialize Q-values to zeros
        self.q_values = np.zeros((num_states, num_actions))

    def select_action(self, state):
        # Exploration-exploitation trade-off
        if np.random.rand() < self.exploration_prob:
            return np.random.choice(self.num_actions)  # Explore
        else:
            return np.argmax(self.q_values[state, :])  # Exploit

    def update_q_values(self, state, action, reward, next_state):
        # Q-value update using the Q-learning formula
        self.q_values[state, action] = (1 - self.learning_rate) * self.q_values[state, action] + \
                                       self.learning_rate * (reward + self.discount_factor * np.max(self.q_values[next_state, :]))

### Step 3. 設定初始地圖(n * m), 設定num_episodes

def run_q_learning():
    # Define the maze as a grid (0: empty, 1: obstacle, 2: goal)
    maze = np.array([
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
        [0, 1, 2, 0, 0, 1, 0, 1, 0, 0],
        [0, 1, 1, 1, 0, 1, 0, 1, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 1, 1, 0, 1, 1, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ])

    num_states = np.prod(maze.shape)
    num_actions = 4  # 4 possible actions: up, down, left, right

    agent = QLearningAgent(num_states, num_actions)

    num_episodes = 2000

    best_reward = float('-inf')
    worst_reward = float('inf')
    total_rewards = []

    # 新增一個列表來儲存每個回合的平均報酬
    episode_rewards = []

    # Track optimal path
    optimal_path = []

    for episode in range(num_episodes):

### step 4. 學習並記錄最佳路徑

while True:
            action = agent.select_action(state)
            episode_path.append(action)  # Record the action

            # Simulate the environment (update the state based on the action)
            next_state = take_action(state, action, maze)
            reward = get_reward(next_state, maze, prev_row, prev_col)
            prev_row, prev_col = np.unravel_index(state, maze.shape)
            
            if reward == -1:  # 走到 1
                has_hit_obstacle = True

            # Update Q-values
            agent.update_q_values(state, action, reward, next_state)

            total_reward += reward
            state = next_state

            if maze.flat[next_state] == 2 :  # Reached the goal
                if (len(optimal_path) > len(episode_path) and not has_hit_obstacle) or len(optimal_path) == 0:
                    optimal_path = episode_path  # Update optimal path
                    # Output the optimal path
                    print("Optimal Path:", optimal_path)
                    print("len:", len(optimal_path))
                    print("times:", episode)
                has_hit_obstacle = False
                break

### step 5. 設置畫布(Average Reward 的折線圖，Q-values 的熱度圖，示最後100次的平均值)

# 設置畫布，建立三個子圖，一行兩列
    fig, (ax1, ax2, ax3) = plt.subplots(1, 3, figsize=(12, 5))

    # 繪製 Average Reward 的折線圖
    ax1.plot(range(1, num_episodes + 1), episode_rewards, label='Average Reward')
    ax1.set_title('Average Reward over Episodes')
    ax1.set_xlabel('Episodes')
    ax1.set_ylabel('Average Reward')
    # ax1.set_ylim(-0.4, 0)
    ax1.legend()
  

    # 繪製 Q-values 的熱度圖在第二個子圖
    im = ax2.imshow(agent.q_values.T, cmap='viridis', aspect='auto', origin='lower')
    ax2.set_title('Q-values Heatmap')
    ax2.set_xlabel('States')
    ax2.set_ylabel('Actions')
    ax2.legend()

    # 繪製第三張圖，表示最後100次的平均值
    ax3 = plt.subplot(1, 3, 3)
    ax3.plot(range(num_episodes - 99, num_episodes + 1), last_100_episode_rewards, label='Average Reward')
    ax3.set_title('Average Reward over Last 100 Episodes')
    ax3.set_xlabel('Episodes')
    ax3.set_ylabel('Average Reward')
    ax3.legend()
    plt.colorbar(im, ax=ax2, label='Q-value')
    plt.tight_layout()
    plt.show()

### Step 6. 設定所有可能之行動

def take_action(state, action, maze):
    # Simulate the environment and return the next state based on the action
    num_cols = maze.shape[1]
    row, col = divmod(state, num_cols)

    if action == 0 :  # Move up
        row = max(0, row - 1)
    elif action == 1:  # Move down
        row = min(maze.shape[0] - 1, row + 1)
    elif action == 2 :  # Move left
        col = max(0, col - 1)
    elif action == 3:  # Move right
        col = min(maze.shape[1] - 1, col + 1)

### Step 7. 設定獎勵機制

def get_reward(state, maze, prev_row, prev_col):
    # Get the current position (row, col) from the flattened state
    row, col = np.unravel_index(state, maze.shape)

    # Check if the agent is at a barrier
    if maze.flat[state] == 1:
        return -1
    # Check if the agent has moved to a new position
    elif row != prev_row or col != prev_col:
        return 0
    # If the agent is still at the same position after the action, apply a penalty
    else:
        return -0.1

### Step 8. main

if __name__ == "__main__":
    run_q_learning()

## Result

    可以發現，一開始模型可能會在原地打轉，但隨著持續的練習，模型在第296次找到了最短距離。這表明模型執行的次數增加並不一定代表模型會立即收斂到最佳策略。為了進一步優化模型的性能，可以考慮實施以下改進策略：

    1.調整探索策略： 初始階段增加探索，以確保模型更全面地探索環境，隨著時間的推移逐漸減少探索機率，使模型更傾向於利用已經學到的知識。

    2.優化學習率： 可以考慮動態調整學習率，例如在初期使用較大的學習率以快速學習，然後逐漸降低學習率以提高穩定性。

    3.調整獎勵和懲罰： 檢查獎勵和懲罰的設定，可能需要調整以更好地反映環境的特性，例如在遇到障礙物時給予更大的懲罰。

    4.增加訓練次數： 如果在第296次找到最短距離，可以考慮增加總的訓練次數，以便模型有更多的機會學到最佳策略。

    5.檢查環境模擬的準確性： 確保環境模擬的實現是正確的，並且 take_action 函數正確模擬了智能體的行為。


綜合以上建議，這些調整和改進可以有助於模型更快地學到最佳策略，並改進一開始在原地打轉的情況



## 完整程式碼

[https://github.com/raypan891108/Reinforcement-Learning.git](https://github.com/raypan891108/Reinforcement-Learning.git)