iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 3
0
AI & Data

強化學習系列 第 3

強化學習筆記 Day 3

前言

昨天提到馬可夫鏈,說明這是一個描述「一連串相關事件所組成的系統,會怎麼隨著時間變化」的數學模型。並提到可以用這個方法計算第 n 次觀察時,小明各狀態的機率。

小明的狀態轉移 (續)

今天我們將接續昨天提到的例子,以 Python 計算小明各狀態的機率確實會收斂,以下先說明我使用的環境與套件,未來幾天的實作也將以這些環境、套件為主。

  • Ubuntu 18.04 LTS
  • Python 3.6.6
  • numpy

不過在 Windows 上也可以執行 Python,安裝方法也很多 (官網下載、Anaconda),這邊就不多做說明。


實作

我們先針對轉移矩陣本身,確認其會不會收斂。

import numpy as np
Matrix_trans = np.array([[0.9,0.1],[0.5,0.5]])

# after n steps
Matrix_trans_step3 = np.linalg.matrix_power(Matrix_trans, 3)
Matrix_trans_step5 = np.linalg.matrix_power(Matrix_trans, 5)
Matrix_trans_step10 = np.linalg.matrix_power(Matrix_trans, 10)
Matrix_trans_step50 = np.linalg.matrix_power(Matrix_trans, 50)
Matrix_trans_step100 = np.linalg.matrix_power(Matrix_trans, 100)

# print the result
print('After 3 steps: \n', Matrix_trans_step3, '\n')
print('After 5 steps: \n', Matrix_trans_step5, '\n')
print('After 10 steps: \n', Matrix_trans_step10, '\n')
print('After 50 steps: \n', Matrix_trans_step50, '\n')
print('After 100 steps: \n', Matrix_trans_step100, '\n')

執行上方內容後,可以得到

After 3 steps:
 [[0.844 0.156]
 [0.78  0.22 ]]

After 5 steps:
 [[0.83504 0.16496]
 [0.8248  0.1752 ]]

After 10 steps:
 [[0.83335081 0.16664919]
 [0.83324595 0.16675405]]

After 50 steps:
 [[0.83333333 0.16666667]
 [0.83333333 0.16666667]]

After 100 steps:
 [[0.83333333 0.16666667]
 [0.83333333 0.16666667]]

表示轉移矩陣本身即會收斂,因此再加上任意狀態,也都會收斂。不論起始的狀態是 或隨機。

# set s0 = [1, 0]
s0 = np.array([1.0, 0.0])

# print the result
print('Initial state: \n', s0, '\n')
print('After 3 steps: \n', np.dot(s0, Matrix_trans_step3), '\n')
print('After 5 steps: \n', np.dot(s0, Matrix_trans_step5), '\n')
print('After 10 steps: \n', np.dot(s0, Matrix_trans_step10), '\n')
print('After 50 steps: \n', np.dot(s0, Matrix_trans_step50), '\n')
print('After 100 steps: \n', np.dot(s0, Matrix_trans_step100), '\n')
 Initial state:
 [1. 0.]

After 3 steps:
 [0.844 0.156]

After 5 steps:
 [0.83504 0.16496]

After 10 steps:
 [0.83335081 0.16664919]

After 50 steps:
 [0.83333333 0.16666667]

After 100 steps:
 [0.83333333 0.16666667]
# random initial state
rand_num = np.random.rand(1)
random_s0 = np.array([rand_num, 1-rand_num]).reshape(2)

# print the result
print('Initial state: \n', random_s0, '\n')
print('After 3 steps: \n', np.dot(random_s0, Matrix_trans_step3), '\n')
print('After 5 steps: \n', np.dot(random_s0, Matrix_trans_step5), '\n')
print('After 10 steps: \n', np.dot(random_s0, Matrix_trans_step10), '\n')
print('After 50 steps: \n', np.dot(random_s0, Matrix_trans_step50), '\n')
print('After 100 steps: \n', np.dot(random_s0, Matrix_trans_step100), '\n')
Initial state:
[0.6913491 0.3086509]

After 3 steps:
[0.82424634 0.17575366]

After 5 steps:
[0.83187941 0.16812059]

After 10 steps:
[0.83331845 0.16668155]

After 50 steps:
[0.83333333 0.16666667]

After 100 steps:
[0.83333333 0.16666667]

限制

那麼,只要符合馬可夫性質,結果都會收斂嗎?針對這個問題,我發現在 Quora 上有人有一樣的疑問,並發現除了馬可夫性質,還有兩個條件需要遵守:

  • 任意狀態能夠轉移到任意其他狀態:狀態之間不一定要可以直接轉移,但必須能夠到達那個狀態。
  • 狀態轉移不是固定的週期 (ex: 1 -> 3 -> 2 -> 4 -> 1 ...)

如果只滿足條件一,那麼最終不會收斂,而是卡在重複的週期中 [example];
如果只滿足條件二,那最終只會在連通的部分收斂 [example];
如果兩個都不滿足,那就在連通的狀態中,會出現重複的週期 [example]。

個人認為版面上再貼程式碼會很亂,所以用外部連結呈現結果。

至此,是針對馬可夫鏈的說明,明天將進入馬可夫決策過程。

Reference

[1] How do I tell whether a Markov chain can converge to equilibrium? [link]


上一篇
強化學習筆記 Day 2
下一篇
強化學習筆記 Day4
系列文
強化學習30

尚未有邦友留言

立即登入留言