Showing Revision 1 created 11/28/2012 by Amara Bot.

1. Title:
   10-07 Solving A Mdp
2. Description:

   Unit 10 07 Solving a MDP.mp4

3. 0 0:00 - 0:02
   Now to solve an MDP,
4. 2000 0:02 - 0:06
   we're trying to find a policy--pi of S--
5. 6000 0:06 - 0:08
   that's going to be our answer.
6. 8000 0:08 - 0:10
   The pi that we want--the optimal policy--
7. 10000 0:10 - 0:13
   is the one that's going to maximize
8. 13000 0:13 - 0:15
   the discounted, total Reward.
9. 15000 0:15 - 0:17
   So what we mean is:
10. 17000 0:17 - 0:20
    we want to take the sum over all Times
11. 20000 0:20 - 0:23
    into the future of the Reward
12. 23000 0:23 - 0:25
    that you get from starting out
13. 25000 0:25 - 0:28
    in the state that you're in, in time T--
14. 28000 0:28 - 0:32
    and then applying the policy to that state,
15. 32000 0:32 - 0:35
    and arriving at a new state, at time T plus 1.
16. 35000 0:35 - 0:37
    And so we want to maximize that sum--
17. 37000 0:37 - 0:39
    but the sum might be infinite
18. 39000 0:39 - 0:41
    and so, what we do is
19. 41000 0:41 - 0:43
    we take this value, Gamma,
20. 43000 0:43 - 0:46
    and raise it to the T power, saying
21. 46000 0:46 - 0:49
    we're going to count future Rewards less than
22. 49000 0:49 - 0:52
    current Rewards--and that way,
23. 52000 0:52 - 0:55
    we'll make sure that the sum total is bounded.
24. 55000 0:55 - 0:58
    So we want the policy that maximizes that result.
25. 58000 0:58 - 1:00
    If we figure out the utility of the state
26. 60000 1:00 - 1:03
    by solving the Markov Decision Process,
27. 63000 1:03 - 1:07
    then we have: the utility of any state, S,
28. 67000 1:07 - 1:09
    is equal to the maximum over all
29. 69000 1:09 - 1:12
    possible actions that we could take in S
30. 72000 1:12 - 1:15
    of the expected value of taking that action.
31. 75000 1:15 - 1:17
    And what's the expected value?
32. 77000 1:17 - 1:21
    Well, it's just the sum over all resulting states
33. 81000 1:21 - 1:23
    of the transition model--
34. 83000 1:23 - 1:25
    the probability that we get to that state,
35. 85000 1:25 - 1:28
    given from the start state, we take an action
36. 88000 1:28 - 1:31
    specified by the optimal policy
37. 91000 1:31 - 1:34
    times the utility of that resulting state.
38. 94000 1:34 - 1:37
    So--look at all possible actions;
39. 97000 1:37 - 1:39
    choose the best one--
40. 99000 1:39 -
    according to the expected, in terms of probability utility.