ݺߣ

ݺߣShare a Scribd company logo

????? ??? Part 1

?
?
D
Dongmin Lee

?????. ???? ????? ???? ?? ???? ???????. Part 1? MDP, ??, ????, ???? ??????? Part 2??? ???? ?????? ??, ????? ??, ??, ?????? ???????. ???? ????? ??? ??????~!

1 of 30
Downloaded 147 times
???? ????? ??? Part 1 - ?? ?? - ???
Reference ? ??? ?? ?? ???? ??????. ?? : ???? ???? ??? ???? ??? ?? : http://wikibook.co.kr/reinforcement-learning
Index 1. MDP 2. ?? 3. ???? 4. ???? ????? ???? ????? ??? Part 1 - ?? ?? -
1. MDP(Markov Decision Process)
1. MDP(Markov Decision Process) ?? = s??(State) ??(Action) ? ? = a ????(Reward Function) ? ? ? = E[??+1|?? = ?, ? ? = ?] ?? ?? ?? (State Transition Probability) ???` ? = P[??+1 = ?`|?? = ?, ? ? = ?] ???(Discount Factor) ? (?, ? [0,1])
2. ??(Policy)
2. ??(Policy) ? ? ? = ?[? ? = ?|?? = ?] ??(Policy)? ??
3. ????(Value Function)
3. ????(Value Function) ????(Value Function) ?? ????(State Value Function) ?? ????(Action Value Function) ??? ???? ???? ? ???? ??? ?? ??? ?? ???? ?? ?? ???? ? ??? ?? ?? ????? ???? ?? ??? ??? ??? ???? ??
3. ????(Value Function) ????(Value Function) ?? ????(State Value Function) ?? ????(Action Value Function) ??? ???? ???? ? ???? ??? ?? ??? ?? ???? ?? ?? ???? ? ??? ?? ?? ????? ???? ?? ??? ??? ??? ???? ??
?? ????(State Value Function) ? ? = ?[??|?? = ?] ? ? = ?[??+1 + ???+2 + ?2 ??+3 + ? |?? = ?] - ?? ????? ?? ? ? = ?[??+1 + ?(??+2 + ???+3 + ? )|?? = ?] - ??? ?? ???? ??? ?? ???? (?? = ??+1 + ???+2 + ?2 ??+3 + ?) - ??? ?? ???? ? ? ?? ??? ?? ???? ? ? = ?[??+1 + ???+1|?? = ?] - ???(?)?? ??? ?? ????
?? ????(State Value Function) ? ? = ?[??+1 + ???+1|?? = ?] - ???(?)?? ??? ?? ???? ? ? = ?[??+1 + ??(??+1)|?? = ?] - ????? ??? ?? ???? ? ? ? = ? ?[??+1 + ?? ?(??+1)|?? = ?] - ??? ??? ?? ???? (? ??+1 = ?[??+1|??+1 = ?])
3. ????(Value Function) ????(Value Function) ?? ????(State Value Function) ?? ????(Action Value Function) ??? ???? ???? ? ???? ??? ?? ??? ?? ???? ?? ?? ???? ? ??? ?? ?? ????? ???? ?? ??? ??? ??? ???? ??
?? ????(Action Value Function) ?? ????(Action Value Function) = ???(Q Function)
???(Q Function) ? ? ? = ? ?? ?(?|?)? ?(?, ?) ? ?(?, ?) = ? ?[??+1 + ?? ?(??+1, ? ?+1)|?? = ?, ? ? = ?] - ???? ?? - ?? ????? ??? ??? ???
4. ???? ????? (Dynamic Programming)
???? ?????(Dynamic Programming, DP)??? ????(Dynamic) ?? ??? (?????? ???? ??? ?? ??? ???) ?????(Programming) ??? ?????? ??? ??? ?? ???? ?? ????? ???? ????? ? + ? ??? ? ?? ?? ?? ???? ??? ??? ?? ? ??? ?? ??? ??? ???? ?.
4. ???? ?????(Dynamic Programming) ? ???? ?????? ?????? ??????
4. ???? ?????(Dynamic Programming) ???? ?????? ??? ????? ??? ??? ?????.
4. ???? ?????(Dynamic Programming) ???? ?????(DP) ?? ?????(Policy Iteration) ?? ?????(Value Iteration) ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ? ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ?
4. ???? ?????(Dynamic Programming) ???? ?????(DP) ?? ?????(Policy Iteration) ?? ?????(Value Iteration) ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ? ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ?
?? ?????(Policy Iteration) ?? ????? = ?? ?? ???? ?? = ?? + ???? = ?? + ?? ????(???) + ?? ????(=???, argmax) = ?? ??(Policy Evaluation) + ?? ?? ??(Greedy Policy Improvement)
?? ?????(Policy Iteration) ?? ????? = ?? ?? ???? ?? = ?? + ???? = ?? + ?? ????(???) + ?? ????(=???, argmax) = ?? ??(Policy Evaluation) + ?? ?? ??(Greedy Policy Improvement)
?? ??(Policy Evaluation) ?? ?? -> ?? ?? ??? ? ? ? = ? ?[??+1 + ?? ?(??+1)|?? = ?] ? ? ? = ? ?? ?(?|?)(??+1 + ? ? ?`? ???` ? ? ?(?`)) - ?? ?? ???? ?? - ?? ??? ?? ?? ??? ? ?+1 ? = ? ?? ?(?|?)(??+1 + ?? ? ?` ) - k? k+1? ??? ?? ?? ??? (?? ?? ?? = 1)
?? ?????(Policy Iteration) ?? ????? = ?? ?? ???? ?? = ?? + ???? = ?? + ?? ????(???) + ?? ????(=???, argmax) = ?? ??(Policy Evaluation) + ?? ?? ??(Greedy Policy Improvement)
?? ?? ??(Greedy Policy Improvement) ?? ?? ?? -> ???(argmax) ???? ?? ?? ??? ??? ?? ??? (?? ?? ?? = 1) - ?? ?? ???? ?? ??? ?? ? ?(?, ?) = ? ?[??+1 + ?? ?(??+1)|?? = ?, ? ? = ?] ? ?(?, ?) = ? ? ? + ?? ?(?`) ?` ? = ?????? ?? ? ?(?, ?)
4. ???? ?????(Dynamic Programming) ???? ?????(DP) ?? ?????(Policy Iteration) ?? ?????(Value Iteration) ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ? ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ?
?? ?????(Value Iteration) ?? ????? = ?? ?? ???? ?? = ?? ????(=???, max) ??(?, ?) = ?[??+1 + ? max ?` ??(??+1, ?`) |?? = ?, ? ? = ?] ?? ? = max ? ?[??+1 + ???(??+1)|?? = ?, ? ? = ?] - ?? ?? ???? ?? - ???? ??? ?? ?? ??? ? ?+1(?) = max ?? (? ? ? + ?? ? ?` ) k? k+1? ??? ?? ??? ?? ?? ??? (?? ?? ?? = 1)
????? ??????
?????.

More Related Content

????? ??? Part 1

  • 1. ???? ????? ??? Part 1 - ?? ?? - ???
  • 2. Reference ? ??? ?? ?? ???? ??????. ?? : ???? ???? ??? ???? ??? ?? : http://wikibook.co.kr/reinforcement-learning
  • 3. Index 1. MDP 2. ?? 3. ???? 4. ???? ????? ???? ????? ??? Part 1 - ?? ?? -
  • 5. 1. MDP(Markov Decision Process) ?? = s??(State) ??(Action) ? ? = a ????(Reward Function) ? ? ? = E[??+1|?? = ?, ? ? = ?] ?? ?? ?? (State Transition Probability) ???` ? = P[??+1 = ?`|?? = ?, ? ? = ?] ???(Discount Factor) ? (?, ? [0,1])
  • 7. 2. ??(Policy) ? ? ? = ?[? ? = ?|?? = ?] ??(Policy)? ??
  • 9. 3. ????(Value Function) ????(Value Function) ?? ????(State Value Function) ?? ????(Action Value Function) ??? ???? ???? ? ???? ??? ?? ??? ?? ???? ?? ?? ???? ? ??? ?? ?? ????? ???? ?? ??? ??? ??? ???? ??
  • 10. 3. ????(Value Function) ????(Value Function) ?? ????(State Value Function) ?? ????(Action Value Function) ??? ???? ???? ? ???? ??? ?? ??? ?? ???? ?? ?? ???? ? ??? ?? ?? ????? ???? ?? ??? ??? ??? ???? ??
  • 11. ?? ????(State Value Function) ? ? = ?[??|?? = ?] ? ? = ?[??+1 + ???+2 + ?2 ??+3 + ? |?? = ?] - ?? ????? ?? ? ? = ?[??+1 + ?(??+2 + ???+3 + ? )|?? = ?] - ??? ?? ???? ??? ?? ???? (?? = ??+1 + ???+2 + ?2 ??+3 + ?) - ??? ?? ???? ? ? ?? ??? ?? ???? ? ? = ?[??+1 + ???+1|?? = ?] - ???(?)?? ??? ?? ????
  • 12. ?? ????(State Value Function) ? ? = ?[??+1 + ???+1|?? = ?] - ???(?)?? ??? ?? ???? ? ? = ?[??+1 + ??(??+1)|?? = ?] - ????? ??? ?? ???? ? ? ? = ? ?[??+1 + ?? ?(??+1)|?? = ?] - ??? ??? ?? ???? (? ??+1 = ?[??+1|??+1 = ?])
  • 13. 3. ????(Value Function) ????(Value Function) ?? ????(State Value Function) ?? ????(Action Value Function) ??? ???? ???? ? ???? ??? ?? ??? ?? ???? ?? ?? ???? ? ??? ?? ?? ????? ???? ?? ??? ??? ??? ???? ??
  • 14. ?? ????(Action Value Function) ?? ????(Action Value Function) = ???(Q Function)
  • 15. ???(Q Function) ? ? ? = ? ?? ?(?|?)? ?(?, ?) ? ?(?, ?) = ? ?[??+1 + ?? ?(??+1, ? ?+1)|?? = ?, ? ? = ?] - ???? ?? - ?? ????? ??? ??? ???
  • 16. 4. ???? ????? (Dynamic Programming)
  • 17. ???? ?????(Dynamic Programming, DP)??? ????(Dynamic) ?? ??? (?????? ???? ??? ?? ??? ???) ?????(Programming) ??? ?????? ??? ??? ?? ???? ?? ????? ???? ????? ? + ? ??? ? ?? ?? ?? ???? ??? ??? ?? ? ??? ?? ??? ??? ???? ?.
  • 18. 4. ???? ?????(Dynamic Programming) ? ???? ?????? ?????? ??????
  • 19. 4. ???? ?????(Dynamic Programming) ???? ?????? ??? ????? ??? ??? ?????.
  • 20. 4. ???? ?????(Dynamic Programming) ???? ?????(DP) ?? ?????(Policy Iteration) ?? ?????(Value Iteration) ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ? ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ?
  • 21. 4. ???? ?????(Dynamic Programming) ???? ?????(DP) ?? ?????(Policy Iteration) ?? ?????(Value Iteration) ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ? ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ?
  • 22. ?? ?????(Policy Iteration) ?? ????? = ?? ?? ???? ?? = ?? + ???? = ?? + ?? ????(???) + ?? ????(=???, argmax) = ?? ??(Policy Evaluation) + ?? ?? ??(Greedy Policy Improvement)
  • 23. ?? ?????(Policy Iteration) ?? ????? = ?? ?? ???? ?? = ?? + ???? = ?? + ?? ????(???) + ?? ????(=???, argmax) = ?? ??(Policy Evaluation) + ?? ?? ??(Greedy Policy Improvement)
  • 24. ?? ??(Policy Evaluation) ?? ?? -> ?? ?? ??? ? ? ? = ? ?[??+1 + ?? ?(??+1)|?? = ?] ? ? ? = ? ?? ?(?|?)(??+1 + ? ? ?`? ???` ? ? ?(?`)) - ?? ?? ???? ?? - ?? ??? ?? ?? ??? ? ?+1 ? = ? ?? ?(?|?)(??+1 + ?? ? ?` ) - k? k+1? ??? ?? ?? ??? (?? ?? ?? = 1)
  • 25. ?? ?????(Policy Iteration) ?? ????? = ?? ?? ???? ?? = ?? + ???? = ?? + ?? ????(???) + ?? ????(=???, argmax) = ?? ??(Policy Evaluation) + ?? ?? ??(Greedy Policy Improvement)
  • 26. ?? ?? ??(Greedy Policy Improvement) ?? ?? ?? -> ???(argmax) ???? ?? ?? ??? ??? ?? ??? (?? ?? ?? = 1) - ?? ?? ???? ?? ??? ?? ? ?(?, ?) = ? ?[??+1 + ?? ?(??+1)|?? = ?, ? ? = ?] ? ?(?, ?) = ? ? ? + ?? ?(?`) ?` ? = ?????? ?? ? ?(?, ?)
  • 27. 4. ???? ?????(Dynamic Programming) ???? ?????(DP) ?? ?????(Policy Iteration) ?? ?????(Value Iteration) ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ? ???? ??????? ?? ?? ???? ???? ???? ?? ?? ??? ?? ?
  • 28. ?? ?????(Value Iteration) ?? ????? = ?? ?? ???? ?? = ?? ????(=???, max) ??(?, ?) = ?[??+1 + ? max ?` ??(??+1, ?`) |?? = ?, ? ? = ?] ?? ? = max ? ?[??+1 + ???(??+1)|?? = ?, ? ? = ?] - ?? ?? ???? ?? - ???? ??? ?? ?? ??? ? ?+1(?) = max ?? (? ? ? + ?? ? ?` ) k? k+1? ??? ?? ??? ?? ?? ??? (?? ?? ?? = 1)