1. AI
Markov Decision Processes
non-deterministic search 를 해야하는 이유는 뭐냐? real world 에서 실제 행동의 결과를 예상하는 것이 불가능 하고, 각기 다른 outcome을 계산하여 action을 취해야 함.
북쪽으로 가고싶다! 라고 했을 때 가고싶은거지 100%로 북쪽으로 이동하는 것은 아님..
80% 확률로 진짜 북쪽으로 가거나, 나머지의 확률로 좌/우 든 다른 방향으로 이동하게 될 수 도 있음 (deterministic search랑 차이가 나는 부분)
Defining MDP
1. A set of States
2. A set of actions
3. A transition function T(s, a, s')
어떤 상태 S에서, a라는 action을 했을 때, S'이 될 확률.
4. A reward function R(s, a, s')
5. A start state
6. (Maybe) a terminal state
deterministic search에서는 그게 goal인지 아닌지에 대해서 굉장히 중요하게 생각했지만, MDP에서는 그렇지 않는 경우가 많음.
reward는 매 step마다 작은 reward인 living award가 있고, goal state에서 좋든 나쁘든 큰 reward를 받게 됨.
Expectimax search 가 MDP를 해결하는 하나의 예가 될거고, MDP를 통해서 강화학습의 기반을 마련하기에 중요.
MDP에서 Markov가 무슨뜻이냐?
future state를 결정하는데, 과거의 state는 중요하지 않고, 단지 current state와 그 상태에서의 action만이 고려된다는 뜻.
"Action outcomes depend only on the current state"
MDP에 plan이 있을 수 있나? - non-deterministic한 경우이기에, 내가 생각한대로 되는 plan이란 있을 수 없다. 다만 어떤 경우에 어떤 판단을 할지에 대한 policy만 있을 뿐!
MDP에서는 모든 policy에 관심있는게 아니라, 마찬가지로 optimal policy를 찾는데 관심이 있다.
Utilities of Sequences
- More or Less? [1,2,3] or [2,3,4]
- Now or Later? [0,0,1] or [1,0,0]
보통의 경우, Now, More 의 선택을 한는게 reasonable함.
value of now decay... 그러므로 시간과 보상의 trade-off 관계가 존재할터.
- Game이 안끝나고, 그냥 안전빵으로 아무것도 안하는 상태가 되면 어떡하나?
3가지 solution
1) 시간에 한정을 함. (100 Step 안에 최선의 선택을 해라!)
2) discounting을 적용
3) 암튼 끝나게 함.
MDP의 quantites
1) The value of state s
2) The value of a q-state
V(s) = MaxQ(s,a)
즉, 특정 상황에서의 Maximum value는 그 state 에서 선택할 수 있는 최선의 action에서 얻을 수 있는 값.
Q(s,a) = SUM (T(s,a,s') {R(s,a,s') + r V*(s')})
즉, 특정한 action에서 얻을 수 있는 maximum value는, 그 액션을 통해 s'으로 가면서 얻는 reward (R(s,a,s'))과, discounting 된 미래 state의 value의 평균! -> 어떤 action을 취할 수 있는 probability를 곱함으로 구함.
V*(s)를 구하는거 자체가 상당히 어렵기 때문에(infinite 상황..), V_k(s)를 구하여 해결하자! -> depth를 limit
