AI 筆記30 - Reinforcement Learning & Markov Decision Process

Reinforcement learning

這是AI的一支，本質上就是一系列連續性decison making的科學。
Agent要從環境的回饋(reward)去改善自己。

與supervised/unsupervised learning不同之處在於：
1. 沒有labeled data
2. 目前的action造成的feedback可能會delay回傳過來，類似horizon effect?
3. sequence of actions決定outcome
4. feedback/observation 和actions之間不是獨立的，也跟其過往觀察到的歷史有關

Applications

目前比較成功的就是自駕系統，以及遊戲對弈（alpha go)。
另外就是chatbots (alexa, courtana, siri,...)。

其實重點就是這是一個trial & error的learning method，有點模仿人類，但好處是機器可以永不停止的trial & error！！！

但是應用在醫療領域就非常麻煩，因為error會死人！

Markov Decision Process (MDP)

MDP是一個在discrete的回合中，用來model sequential decision making的model。好拗口！

目前的state（例如目前robot的運動狀態，所在地點等等）已經把過往的所有訊息呈現在其中了，未來的rewards根據目前的action決定。

MDP是以Markov property來define：給予目前的state來說，未來與過去無關！意思是所有未來的state/rewards都已經被目前的MDP captured了。

一個agent一開始在initial state s1，在每個回合t時，觀察到state St，進行某個action At，並且得到reward Rt，並且進入下個state St+1，而Markov Property在這setting下的數學式描述如下：



錯吧？後者應該等於Pr(St+1 = S' | St = S, At = a)？已經寫信去問edX助教了，怪怪的看起來就是錯的（的確是印錯了，見下段綠色部分）。第二行是說expected rewards在任意時間點t也是只跟目前的state/action有關。這些probability可以用matrix P和R表示，每個entry就是一個probability with state and action。

MDP Goal 

MDP的goal是由不同時間點的reward整體考量的，目前常見有3種reward方式組成的goal function：
1. finite time total reward: 這就是單純把有限時間T內的reward加總:

2. infinite time average reward: 這個考慮了所有時間點的reward，取平均值。所以很早之前的rounds對整體的reward影響很輕微。

3. discounted (折現？）sum of rewards: 這個給越接近現在時間點的reward給的權重越大(這考慮到未來的不確定性），而且數學上保證會converge:

gamma稱為discount factor，這是目前最常用的形式。

MDP formalization

上面說可能有錯的地方，在這個slide印證了：