Markov decision process - Revision history

Sára at 22:04, 14 January 2021

2021-01-14T22:04:24Z

Sára at 22:01, 14 January 2021

2021-01-14T22:01:50Z

Sára at 20:54, 13 January 2021

2021-01-13T20:54:31Z

Sára at 22:12, 12 January 2021

2021-01-12T22:12:45Z

Sára at 22:32, 9 January 2021

2021-01-09T22:32:44Z

Sára at 22:23, 9 January 2021

2021-01-09T22:23:35Z

Sára at 21:26, 9 January 2021

2021-01-09T21:26:15Z

Sára at 22:28, 8 January 2021

2021-01-08T22:28:09Z

Sára at 21:58, 8 January 2021

2021-01-08T21:58:34Z

Sára at 22:11, 5 January 2021

2021-01-05T22:11:50Z

@@ Line 139: / Line 139: @@
 States: start of a new round, end of the game, tossing a coin
 Actions: stay, quit
 Rewards: 4, 10, 20, -8 dollars

@@ Line 46: / Line 46: @@
 <math>G_t = R_{\text{t+1}} + \gamma R_{\text{t+2}} + ... = \sum_{k = 0}^\infty\gamma^k R_{\text{t+k+1}}</math>
-We establish sum over all returns in order to avoid situation when we pick an action that will give us decent reward now but will miss better strategy in long term. In the formula we use discounting factor because futher the reward is less certain it is. Value of discounting factor is with the interval [0, 1]. Further into future we go closer to 0 the discounting factor is.
+We establish sum over all returns in order to avoid situation when we pick an action that will give us decent reward now but will miss better strategy in long term. In the formula we use discounting factor because futher the reward is less certain and often less important. Value of discounting factor is with the interval [0, 1]. Further into future we go closer to 0 the discounting factor is.
 === Policy ===
-Policy is the thought behind making some decision. Policy is a function for mapping from each state s from all possible states to an action a from all possible actions. In other words it optimizes the best action that should be taken from each state that an agent can end up in, in order to maximize the return function <math>G_t = R_{\text{t+1}} + \gamma R_{\text{t+2}} + ... = \sum_{k = 0}^\infty\gamma^k R_{\text{t+k+1}}</math> (to get as big as reward as possible when facing possible infinite horizon). Because ending in some state is often not deterministic we follow a random path when we follow the policy. When defining a policy i need to use expected utility because of the randomness.
+Firstly let's establish a function for determining value of a given state, when we have some policy set (in other words, at some state I obey the rule of taking the same action everytime).
 <math>V_\pi(s) = \sum_{\text{s'}} T(s, a, s') [R(s, a, s') + \gamma V_\pi(s')]</math>
-This function tells me the value of policy <math>\pi</math> applied at state s, which is equal to sum over all possible states s' i can end up (with some transition probability T(s, a, s') in where we sum expected immediate reward R after taking the action a and value of the same policy at state s' after taking discount factor into consideration.
+This function makes to sum over all possible states s' i can end up (with some transition probability T(s, a, s') in where we sum expected immediate reward R after taking the action a and value of the same policy at state s' after taking discount factor into consideration.
 So now I my task is to find the optimal policy, the policy which gives me maximum reward.
@@ Line 61: / Line 60: @@
 <math>V_{\text{opt}}(s) = \sum_{\text{s'}} T(s, a, s') [R(s, a, s') + \gamma V_{\text{opt}}(s')]</math>
-For this maximum reward function I get optimum policy function as follows:
+Here I don't have explicitly given action I need to take at state s, I compute value for all possible actions and choose the highest one.
 <math>\pi_{\text{opt}}(s) = argmax_a \Bigl\{ \sum_{\text{s'}} T(s, a, s') [R(s, a, s') + \gamma V_{\text{opt}}(s')] \Bigr\}</math>
 === Reinforcement Learning ===
@@ Line 122: / Line 125: @@
 <math>V_\pi(stay) = \frac{1}{3} 4 + \frac{2}{3} (4 + V_\pi(stay))</math>
-<math>V_\pi(stay) = 4 + \frac{2}{3} (4 + V_\pi(stay))</math>
+<math>V_\pi(stay) = 4 + \frac{2}{3} (V_\pi(stay))</math>
-<math>4 = \frac{2}{3} (4 + V_\pi(stay))</math>
+<math>12 = 4 + \frac{2}{3} (12)</math>
 <math>V_\pi(stay) = 12</math>
 ''Let's now widen our example a little bit and see how it will change''
-Now after rolling a dice and the result is 1 or 2 I am in state when I have to toss a coin and if it is head I get 12 dollars and the game is over otherwise i loose 8 dollars and the game is over.
+Now after rolling a dice and the result is 1 or 2 I am in state when I have to toss a coin and if it is head I get 20 dollars and the game is over otherwise i loose 8 dollars and the game is over.
 Here are the updates I have done:
 States: start of a new round, end of the game, tossing a coin
 Actions: stay, quit
-Rewards: 4, 10, 12, -8 dollars
+Rewards: 4, 10, 20, -8 dollars
 When I decide to quit nothing changes. If I decide to stay I get 4 dollars and can with probability of 67% start a new round or with 33% probability I'm in the state when I got 1 or 2 after rolling the dice and I toss a coin and with probability of 50% I will loose 8 dollars and end the game and same probability of gaining 12 dollars and ending the game.
@@ Line 144: / Line 149: @@
 <math>V_\pi(stay) = \frac{1}{3} (4 + V_\pi(toss)) + \frac{2}{3} (4 + V_\pi(stay))</math>
-Expected value of toss is 0.5*-8 + 0.5*12= 2.
+Expected value of toss is 0.5*-8 + 0.5*20= 6 and then the game ends, so it means that we won't have any further states that have to be taken into consideration.
 =Zdroje=

@@ Line 118: / Line 118: @@
 <math>V_\pi(stay) = \frac{1}{3} (4 + V_\pi(end)) + \frac{2}{3} (4 + V_\pi(stay))</math>
-we know that the expected reward of policy 'stay' is 0, as after the end of the game we won't get any more money, so let's write it into our formula.
+we know that the expected reward of policy 'end' is 0, as after the end of the game we won't get any more money, so let's write it into our formula.
 <math>V_\pi(stay) = \frac{1}{3} 4 + \frac{2}{3} (4 + V_\pi(stay))</math>
@@ Line 130: / Line 130: @@
 ''Let's now widen our example a little bit and see how it will change''
-Now after rolling a dice and the result is 1 or 2 I am in state when I have to toss a coin and if it is head I get 15 dollars and the game is over otherwise i loose 8 dollars and the game is over or I can ask to roll dice again but loosing 1 dollar.
+Now after rolling a dice and the result is 1 or 2 I am in state when I have to toss a coin and if it is head I get 12 dollars and the game is over otherwise i loose 8 dollars and the game is over.
 Here are the updates I have done:
-States: start of a new round, end of the game, dice resulted in 1 or 2
+States: start of a new round, end of the game, tossing a coin
-Actions: stay, quit, toss a coin, ask to roll the dice again
+Actions: stay, quit
-Rewards: 4, 10, 15, -8, -1 dollars
+Rewards: 4, 10, 12, -8 dollars
-When I decide to quit nothing changes. If I decide to stay I get 4 dollars and can with probability of 67% start a new round or with 33% probability I'm in the state when I got 1 or 2 after rolling the dice and I can either roll the dice again and have the same probabilities and same states as in case of stay action but I will loose 1 dollar, or I can try to toss a coin and with probability of 50% I will loose 8 dollars and end the game and same probability of gaining 15 dollars and ending the game.
+When I decide to quit nothing changes. If I decide to stay I get 4 dollars and can with probability of 67% start a new round or with 33% probability I'm in the state when I got 1 or 2 after rolling the dice and I toss a coin and with probability of 50% I will loose 8 dollars and end the game and same probability of gaining 12 dollars and ending the game.
 Let's now calculate the expected value of state 'at the end of a new round' with the action 'stay'.
 =Zdroje=

← Older revision		Revision as of 22:12, 12 January 2021
Line 139:		Line 139:
	When I decide to quit nothing changes. If I decide to stay I get 4 dollars and can with probability of 67% start a new round or with 33% probability I'm in the state when I got 1 or 2 after rolling the dice and I can either roll the dice again and have the same probabilities and same states as in case of stay action but I will loose 1 dollar, or I can try to toss a coin and with probability of 50% I will loose 8 dollars and end the game and same probability of gaining 15 dollars and ending the game.		When I decide to quit nothing changes. If I decide to stay I get 4 dollars and can with probability of 67% start a new round or with 33% probability I'm in the state when I got 1 or 2 after rolling the dice and I can either roll the dice again and have the same probabilities and same states as in case of stay action but I will loose 1 dollar, or I can try to toss a coin and with probability of 50% I will loose 8 dollars and end the game and same probability of gaining 15 dollars and ending the game.
	Let's now calculate the expected value of state 'at the end of a new round' with the action 'stay'.		Let's now calculate the expected value of state 'at the end of a new round' with the action 'stay'.
		+
		+	=Zdroje=
		+
		+	==Articles==
		+	[https://towardsdatascience.com/getting-started-with-markov-decision-processes-reinforcement-learning-ada7b4572ffb]
		+	[https://www.worldscientific.com/doi/suppl/10.1142/p809/suppl_file/p809_chap01.pdf]
		+	[https://towardsdatascience.com/reinforcement-learning-demystified-markov-decision-processes-part-1-bf00dda41690]
		+
		+	==Videos==
		+	[https://www.youtube.com/watch?v=9g32v7bK3Co&list=PLoROMvodv4rO1NB9TD4iUZ3qghGEGtqNX&index=7]
		+	[https://www.youtube.com/watch?v=sdp49vTanSk]

@@ Line 108: / Line 108: @@
 Actions: to quit, to continue
-Reward: 4 dollars / 10 dollars
+Rewards: 4 dollars, 10 dollars
 When a robot is in state when a new round starts, it has 2 actions it can takes, either it can quit the game, or continue. If the robot quits the game it is 100% certain that it will get 10 dollars. If the robot decides to take risk it will get 4 dollars and with 67% probability. However there is also 33% probability of getting 4 dollars, but after rolling a dice, the dice will result in 1 or 2 a thus quits the game.
@@ Line 130: / Line 130: @@
 ''Let's now widen our example a little bit and see how it will change''
-Now after rolling a dice and the result is 1 or 2 I am in state when I have to toss a coin and if it is head I get 15 dollars and the game is over otherwise i loose 8 dollars and the game is over.
+Now after rolling a dice and the result is 1 or 2 I am in state when I have to toss a coin and if it is head I get 15 dollars and the game is over otherwise i loose 8 dollars and the game is over or I can ask to roll dice again but loosing 1 dollar.

@@ Line 64: / Line 64: @@
 <math>\pi_{\text{opt}}(s) = argmax_a \Bigl\{ \sum_{\text{s'}} T(s, a, s') [R(s, a, s') + \gamma V_{\text{opt}}(s')] \Bigr\}</math>
 === Value Iteration ===
@@ Line 78: / Line 92: @@
-The time complexity of this algorithm is <math>O(tSS')</math> because i iterate t-times over S possible states and these states are S' possible next states. The reason why we don't take actions into account is that i'm calculating the policy for all states and for each state i have exactly one action I take every time I end up in this particular actions.
+The time complexity of this algorithm is <math>O(tSS')</math> because i iterate t-times over S possible states and these states are S' possible next states. The reason why we don't take actions into account is that i'm calculating the policy for all states and for each state i have exactly one action I take every time I end up in this particular actions, in other word my policy is already set.
 When calculating optimal policy the complexity of this algorithm is <math>O(tSAS')</math> as we take all possible actions available at given state into consideration and choose one that provides us with the biggest reward.
 == MDP Applications ==
-=== Example 1 ===
+=== Example ===
 Imagine we play a game. The game is played in rules. In each rule you get to decide whether you want to quit or continue. If you quit you get 10 dollars and the game is over however if you continue i will give you 4 dollars and roll a 6-sided dice, if the dice results in 1 or 2 the game is over otherwise we start another round.
 First let us list all MDP variables according to terminology.
@@ Line 113: / Line 127: @@
 <math>V_\pi(stay) = 12</math>

@@ Line 41: / Line 41: @@
 Without actions state transitions would be stochastic (random). Now the agent can control its own fate to some extent.
- Let's imagine now our automatic vacuum cleaner. It can be in a state, where it can decide from more options, which action to take. After taking each of available actions it can find itself in some other state with some probability. Sum over probabilities of all possible states, that the vacuum cleaner can end up in has to be equal to 1. For example if the vacuum cleaner is next to a sofa it can decide to either avoid it or try to get under the sofa and clean the area there. If it decides to go under the sofa there is 20% that if will not fit there and get damaged, 70% probability that it will clean it successfully and 10% probability that it will clean the area but get stuck there. So if we sum probabilities of all possible states after taking particular action it has to be 1. In our case 0.2 (next state is damaged) + 0.7 (next state next to a sofa after cleaning the area under it) + 0.1 (are is cleaned but it is stuck under the sofa) is equal to 1.
+Let's imagine now our automatic vacuum cleaner. It can be in a state, where it can decide from more options, which action to take. After taking each of available actions it can find itself in some other state with some probability. Sum over probabilities of all possible states, that the vacuum cleaner can end up in has to be equal to 1. For example if the vacuum cleaner is next to a sofa it can decide to either avoid it or try to get under the sofa and clean the area there. If it decides to go under the sofa there is 20% that if will not fit there and get damaged, 70% probability that it will clean it successfully and 10% probability that it will clean the area but get stuck there. So if we sum probabilities of all possible states after taking particular action it has to be 1. In our case 0.2 (next state is damaged) + 0.7 (next state next to a sofa after cleaning the area under it) + 0.1 (are is cleaned but it is stuck under the sofa) is equal to 1.
 === Return ===
@@ Line 51: / Line 51: @@
 <math>\pi (a | s) = P[A_t = a | S_t = s]</math>
-Policy is the thought behind making some decision. Policy is a function for mapping from each states s from all possible states to an action a from all possible actions. In other words it optimizes the best action that should be taken from each state that an agent can end up in, in order to maximize the return function mentioned above (to get as big as reward as possible when facing possible infinite horizon). Because ending in some state is often not deterministic we follow a random path when we follow the policy. When defining a policy i need to use expected utility because of the randomness.
+Policy is the thought behind making some decision. Policy is a function for mapping from each state s from all possible states to an action a from all possible actions. In other words it optimizes the best action that should be taken from each state that an agent can end up in, in order to maximize the return function <math>G_t = R_{\text{t+1}} + \gamma R_{\text{t+2}} + ... = \sum_{k = 0}^\infty\gamma^k R_{\text{t+k+1}}</math> (to get as big as reward as possible when facing possible infinite horizon). Because ending in some state is often not deterministic we follow a random path when we follow the policy. When defining a policy i need to use expected utility because of the randomness.
-<math>V_\pi(s) = \sum_s' T(s, a, s') [R(s, a, s') + \gamma V_\pi(s')]</math>
+<math>V_\pi(s) = \sum_{\text{s'}} T(s, a, s') [R(s, a, s') + \gamma V_\pi(s')]</math>
-This function tells me the value of policy <math>\pi</math> applied at state s, which is equal to sum over all possible states s' i can end up in where we sum expected immediate reward R after taking the action a and value of the same policy at state s' after taking discount factor into consideration.
+This function tells me the value of policy <math>\pi</math> applied at state s, which is equal to sum over all possible states s' i can end up (with some transition probability T(s, a, s') in where we sum expected immediate reward R after taking the action a and value of the same policy at state s' after taking discount factor into consideration.
 === Value Iteration ===
-Using this algorithm we calculate the value of each policy we can apply at given state s.
+Using this algorithm we calculate the value of expected reward at the state s given that we use certain policy, for example i decide to alway steer right when I am at a crossroad.
 The approach is this: Start with arbitrary policy values and repeatedly apply recurrences to converge to true values. However complicated this definition sounds, it is quite straightforward.
@@ Line 65: / Line 73: @@
 Then i start a loop of t iterations. For each iteration i will update value of each state depending on the value from previous iteration.
-<math>V_\pi^{\text{(t)}}(s) = \sum_s' T(s, a, s') [R(s, a, s') + \gamma V_\pi^{\text{(t-1)}}(s')]</math>
+<math>V_\pi^{\text{(t)}}(s) = \sum_{\text{s'}} T(s, a, s') [R(s, a, s') + \gamma V_\pi^{\text{(t-1)}}(s')]</math>
-When we consider the value of t, which stands for number of iterations. We mostly set the t with reflection to change in values of given policy during iterations. So if the change drops under some value i stop the iteration and i take the results from my last iteration as values of all policies given all possible states.
+We iterate repeatedly values for all states until V converges with left-hand side equal to right hand side. When we make iterations for the whole policy we usually iterate until difference between value at state s' hasn't changed much from state s.
 The time complexity of this algorithm is <math>O(tSS')</math> because i iterate t-times over S possible states and these states are S' possible next states. The reason why we don't take actions into account is that i'm calculating the policy for all states and for each state i have exactly one action I take every time I end up in this particular actions.
 == MDP Applications ==

← Older revision		Revision as of 22:28, 8 January 2021
Line 57:		Line 57:
	This function tells me the value of policy <math>\pi</math> applied at state s, which is equal to sum over all possible states s' i can end up in where we sum expected immediate reward R after taking the action a and value of the same policy at state s' after taking discount factor into consideration.		This function tells me the value of policy <math>\pi</math> applied at state s, which is equal to sum over all possible states s' i can end up in where we sum expected immediate reward R after taking the action a and value of the same policy at state s' after taking discount factor into consideration.

		+	=== Value Iteration ===
		+	Using this algorithm we calculate the value of each policy we can apply at given state s.
		+	The approach is this: Start with arbitrary policy values and repeatedly apply recurrences to converge to true values. However complicated this definition sounds, it is quite straightforward.
		+
		+	In first step we initialize values for each policy at given state to 0.
		+
		+	Then i start a loop of t iterations. For each iteration i will update value of each state depending on the value from previous iteration.
		+
		+	<math>V_\pi^{\text{(t)}}(s) = \sum_s' T(s, a, s') [R(s, a, s') + \gamma V_\pi^{\text{(t-1)}}(s')]</math>
		+
		+	When we consider the value of t, which stands for number of iterations. We mostly set the t with reflection to change in values of given policy during iterations. So if the change drops under some value i stop the iteration and i take the results from my last iteration as values of all policies given all possible states.
		+
		+
		+	The time complexity of this algorithm is <math>O(tSS')</math> because i iterate t-times over S possible states and these states are S' possible next states. The reason why we don't take actions into account is that i'm calculating the policy for all states and for each state i have exactly one action I take every time I end up in this particular actions.

	== MDP Applications ==		== MDP Applications ==

@@ Line 40: / Line 40: @@
 Without actions state transitions would be stochastic (random). Now the agent can control its own fate to some extent.
 === Return ===
@@ Line 49: / Line 51: @@
 <math>\pi (a | s) = P[A_t = a | S_t = s]</math>
-Policy is the thought behind making some decision. Formally it is a probability distribution over actions a available at the current state s.
+Policy is the thought behind making some decision. Policy is a function for mapping from each states s from all possible states to an action a from all possible actions. In other words it optimizes the best action that should be taken from each state that an agent can end up in, in order to maximize the return function mentioned above (to get as big as reward as possible when facing possible infinite horizon). Because ending in some state is often not deterministic we follow a random path when we follow the policy. When defining a policy i need to use expected utility because of the randomness.
 == MDP Applications ==
@@ Line 59: / Line 66: @@
 Agent: a robot
 Enviroment: in this case it is not important for the process
 State: at the start of a new round / out of the game
 Actions: to quit, to continue
 Reward: 4 dollars / 10 dollars
-When a robot is in state when a new round starts, it has 2 actions it can takes, either it can quit the game, or continue. If the robot quits the game it is 100% certain that it will get 10 dollars. If the robot decides to take risk it will get 4 dollars and with 67% probability get to another round where it will get an option to obtain another 4 or 10 dollars. However there is also 33% probability that after rolling a dice, the dice will result in 1 or 2 a thus quits the game.
+When a robot is in state when a new round starts, it has 2 actions it can takes, either it can quit the game, or continue. If the robot quits the game it is 100% certain that it will get 10 dollars. If the robot decides to take risk it will get 4 dollars and with 67% probability. However there is also 33% probability of getting 4 dollars, but after rolling a dice, the dice will result in 1 or 2 a thus quits the game.
 In this example we can see Markov property in a way that current state depends solely on previous state. So for us it is not important in what nubmer the dice resulted 2 rounds ago, the most important for us is that in last round dice resulted in number 4 and it gave us green for next round.