Answers.Body: <p>The good news is that:</p>
  
  <ul>
  <li><p>Your MDP appears valid, with well-defined states, actions. It has state transition and reward functions (which you have implemented as matrices). There is nothing else to add, it's a full MDP.</p></li>
  <li><p>You could use this MDP to evaluate a policy, using a variety of reinforcement learning (RL) methods suitable for finite discrete MDPS. For instance, Dynamic Programming could be used, or Monte Carlo or SARSA.</p></li>
  <li><p>You could use this MDP to find an optimal policy for the environment it represents, again using a variety of RL methods, such as Value Iteration, Monte Carlo Control, SARSA or Q-Learning.</p></li>
  </ul>
  
  <p>The bad news is that:</p>
  
  <ul>
  <li><p>All policies in the MDP as defined are optimal, with expected returns (total reward summed until end of episode) of <span class="math-container">$v(S1) = 55, v(S2) = 33.75, v(S3) = 21.25$</span> - solved using Dynamic Programming in case you are wondering.</p></li>
  <li><p>The MDP is degenerate because action choice has no impact on either state transition or reward. It is effectively a <a href="https://en.wikipedia.org/wiki/Markov_reward_model" rel="nofollow noreferrer">Markov Reward Process</a> (MRP) because the agent policy has been made irrelevant.</p></li>
  <li><p>Without discounting, the best result is not going from S1-S4 directly, as you appear to want, but repeatedly looping S1-S3-S2-S1-S3-S2... (this is currently hiiden by action choice being irrelevant). </p>
  
  <ul>
  <li>There are a few ways to fix this, but maybe the simplest is to make the rewards more straightforward (e.g. +0, +10, +20, +30 for S1-S1, S1-S2..., -10, 0, +10, +20 for S2-S1, S2-S2...) and add a discount factor, often labelled <span class="math-container">$\gamma$</span>, when calculating values. A discount factor makes immediate rewards have higher value to the agent, so it will prefer to get a larger reward all at once and end the episode than loop around before finishing.</li>
  </ul></li>
  </ul>
  
  <p>This whole "bad news" section should not worry you too much though. Instead it points to a different issue. The key point is here:</p>
  
  <blockquote>
    <p>The model i have is a pretty uncertain one so i am guessing the agent must initially be given a lot of experience to make any sense of the environment. </p>
  </blockquote>
  
  <p>It looks like you have assumed that you need to explicitly build a MDP model of your environment in order to progress with your problem. So you are providing an inaccurate model, and expect that RL works with that, improving it as part of searching for an optimal policy. </p>
  
  <p>There are a few different approaches you could take in order to learn a model. In this case as your number of states and actions are very low, then you could do it like this:</p>
  
  <ul>
  <li><p>Create a 2D tensor (i.e. just a matrix) to count number of times each state, action pair is visited, initialised with all zeroes, and indexed using S, A</p></li>
  <li><p>Create a 3D tensor to count number of times each state transition is observed, again initialised with all zeroes, indexed using S, A, S'.</p></li>
  <li><p>Run a large number of iterations with the real environment, choosing actions at random, and adding +1 to each visited S, A pair in the first tensor, and +1 to each S, A, S' triple in the second tensor.</p></li>
  <li><p>You now have an approximate transition function based on real experience, without needing an initial guess, or anything particularly clever, you are just taking averages in a table. Divide each count of S, A, S' by the total count of S, A to get conditional transition probability <span class="math-container">$p(s'|s,a)$</span>. It's not really an established, named RL method, but will do.</p></li>
  </ul>
  
  <p>However, if your construction of the MDP is just step 1 for running some RL policy optimisation approach, none of that is really necessary. Instead, you can use a model-free approach such as <a href="https://www.learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/" rel="nofollow noreferrer">tabular Q learning</a> to learn directly online from interactions with the environment. This is likely to be more efficient than learning the model first or alongside the policy optimisation. You don't need the explicit MDP model at all, and adding one can make things more complex - in your case for no real gain.</p>
  
  <p>You probably do still need to define a reward function in your case as there is no inherent reward in the system. You want the agent to reach state S4 as quickly as possible, so you need to monitor the states observed and add a reward signal that is appropriate for this goal. As above, I suggest you modify your planned reward structure to be simple/linear and add discounting to capture the requirement to "increase" state as fast as possible (here I am assuming that being in S2 is still somehow better than being in S1 - if that's not the case, and reaching S4 is the only real goal, then you could simplify further). That's because if you make the rewards for state progression non-linear - as in your example - the agent may find loops that exploit the shape of the reward function and not work to progress states towards S4 as you want.</p>
  
  <p>Beyond this very simple looking environment, there are use cases for systems that learn transition models alongside optimal policies. Whether or not to use them will depend on other qualities of your environment, such as how cheap/fast it is to get real experience of the environment. Using a learned model can help by doing more optimisation with the same raw data, using it to simulate and plan in between taking real actions. However, if the real environment data is very easy to collect, then there may be no point to that.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-06T10:26:28.557Z
Answers.Text: Wow ! I cannot thank you enough for such a descriptive answer and explaining where I am going wrong. Things are pretty clear now .. Except one question in tabular Q-learning method you suggested. They have explained the reward and Q tables as a function of (state,action). For my problem i will have to consider the next state as well (ex. since S2 to S1 cannot be given same reward). Can i use the same concept explained there except I change the reward and Q tables to be functions of (current state,next state,action)? Then # of those tables == #actions for reward and Q tables.
Answers.UserDisplayName: Bhavana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-06T10:28:56.510Z
Answers.Text: The format will be same as the reward table i have mentioned with current states in rows and next states in columns. Just that this will get complicated if i want to add more actions .. But would this way work ?
Answers.UserDisplayName: Bhavana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-06T12:02:47.043Z
Answers.Text: You can change the reward function to match your problem, and it can depend on s,a,s' and also be stochastic, so you are fine with your proposed change. The Q table must be a function of state, action only, to match Q(s,a). You don't *define* that at the start- it is what the agent learns. It will correctly figure out the _expected_ stats, which is what it is for, so don't worry about adding s' to Q.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-05T17:31:32.990Z
Answers.LastActivityDate: 2019-09-05T21:39:00.713Z
Answers.LastEditDate: 2019-09-05T21:39:00.713Z
Answers.UserDisplayName: Neil Slater
Body: <p><strong>Problem Statement :</strong> 
  I have a system with four states - S1 through S4 where S1 is the beginning state and S4 is the end/terminal state. The next state is always better than the previous state i.e if the agent is at S2, it is in a slightly more desirable state than S1 and so on with S4 being the most desirable i.e terminal state. We have two different actions which can be performed on any of these states without restrictions. 
  Our goal is to make the agent reach state S4 from S1 in the most optimal way i.e the route with maximum reward (or minimum cost). The model i have is a pretty uncertain one so i am guessing the agent must initially be given a lot of experience to make any sense of the environment. The MDP i have designed is shown below : </p>
  
  <p><strong>MDP Formulation :</strong> 
  <a href="https://i.sstatic.net/GuymJ.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GuymJ.jpg" alt="MDP for the problem"></a></p>
  
  <p>The MDP might a look a bit messy and complicated but it basically is just showing that any action (A1 or A2) can be taken at any state (except the terminal state S4). The probability with which the transition takes place from one state to the other and the associated rewards are given below. </p>
  
  <p><strong>States :</strong> States S1 to S4. S4 is terminal state and S1 is the beginning state. S2 is a better state than S1 and S3 is a better state than S1 or S2 and S4 is the final state we expect the agent to end up in. </p>
  
  <p><strong>Actions :</strong> Available actions are A1 and A2 which can be taken at any state (except of course the terminal state S4).  </p>
  
  <p><strong>State Transition Probability Matrix :</strong> One action taken at a particular state S can lead to any of the other available states. For ex. taking action A1 on S1 can lead the agent to S1 itself or S2 or S3 or even directly S4. Same goes for A2. So i have assumed an equal probability of 25% or 0.25 as the state transition probability. The state transition probability matrix is the same for actions A1 and A2. I have just mentioned it for one action but it is the same for the other action too. Below is the matrix I created - 
  <a href="https://i.sstatic.net/lfyOS.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lfyOS.jpg" alt="State transition probability matrix for both the actions"></a></p>
  
  <p><strong>Reward Matrix :</strong> The reward function i have considered is a function of the action, current state and future state - R(A,S,S'). The desired route must go from S1 to S4. I have awarded positive rewards for actions that take the agent from S1 to S2 or S1 to S3 or S1 to S4 and similarly for states S2 and S3. A larger reward is given when the agent moves more than one step i.e S1 to S3 or S1 to S4. What is not desired is when the agent gets back to a previous state because of a action. So i have awarded negative rewards when the state goes back to a previous state. The reward matrix currently is the same for both the actions (meaning both A1 and A2 have same importance but it can be altered if A1/A2 is preferred over the other). Following is the reward matrix i created (same matrix for both the actions) - </p>
  
  <p><a href="https://i.sstatic.net/9HX88.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9HX88.jpg" alt="Reward matrix R(A,S,S&#39;) for both the actions"></a></p>
  
  <p><strong>Policy, Value Functions and moving forward :</strong> 
  Now that i have defined my states, actions, rewards, transition probabilities the next step I guess i need to take is to find the optimal policy. I do not have an optimal value function or policy. From lot of googling i did, I am guessing i should start with a random policy i.e both actions have equal probability of being taken at any given state -> compute the value function for each state -> compute the value functions iteratively until they converge -> then find the optimal policy from the optimal value functions. </p>
  
  <p>I am totally new to RL and all the above knowledge is from whatever i have gathered reading online. Can someone please validate my solution and MDP if I am going the right way? If the MDP i created will work ? 
  Apologies for such a big write-up but i just wanted to clearly depict my problem statement and solution. If the MDP is ok then can someone also help me with how can the value function iteratively converge to an optimal value? I have seen lot of examples which are deterministic but none for stochastic/random processes like mine. </p>
  
  <p>Any help/pointers on this would be greatly appreciated. 
  Thank you in advance  </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:17:27.163Z
Comments.Text: As defined there is no difference at all between the actions, and there is nothing to optimise (the agent will get the same expected reward regardless of what it does). However, you say this might change. On what basis will it change? Is this a toy problem to help you understand how optimising MDPs should work, so you can make arbitrary changes to help you learn? Or is it representing something real that you want to optimise?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:28:04.240Z
Comments.Text: Would you suggest I have different reward function for both the actions?
Comments.UserDisplayName: Bhavana
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:28:30.763Z
Comments.Text: Your transition matrix says that the actions have no influence at all on the state transition, or on the reward. Probably I can base an answer on that. Also you cannot have "Another A2" The name A2 needs to fully specify the action taken. If there are choices to make *inside* the action, then that needs to be part of the MDP explicitly
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:30:52.067Z
Comments.Text: Well what i assumed was the state transition probabilities would be learnt by the agent. Initially an action on a state can lead to any of the other states. Unless until the agent/simulator is run with that action we wouldnt know which state it would land up in.
Comments.UserDisplayName: Bhavana
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:34:48.227Z
Comments.Text: What does this mean - If there are choices to make inside the action ?
Comments.UserDisplayName: Bhavana
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:40:16.190Z
Comments.Text: Oh right, so the state transitions are not the real state transitions - you have a "real" system with unknonws that you want an agent to learn? You don't need an explicit MDP model for the agent to learn optimal behaviour. But you might if you want to run a simulator of the environment to test an agent then of course you need to define something . . . it doesn't need to be a full MDP model, but that is OK, and might be instructive.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:40:49.317Z
Comments.Text: "What does this mean - If there are choices to make inside the action ?". You said "Another A2" - what is different between the two A2 actions that you are thinking of?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:45:37.953Z
Comments.Text: Right these are not real state transitions. But I would like the agent to learn and find out what the exact transitions are. So until then I assume it to be equal probability because I don't know which action on which action might lead to which state.  So what do you suggest how can I approach this problem ??
Comments.UserDisplayName: Bhavana
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:53:07.170Z
Comments.Text: Bhavana: OK, that makes more sense - you are talking about model learning, and assuming that RL needs to learn the underlying model. It can do, but much RL does not do this. For instance, Q Learning does not learn the MDP model. Do you actually want the agent to learn an accurate MDP model? I think I can answer your question as phrased here (and may do so later), but you should bear in mind that it may be leading you in the wrong direction, and that if what you want to do is learn an optimal policy for your microcontroller, it is not necessary to model the MDP directly
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T15:59:20.600Z
Comments.Text: Oh!! I am sorry I am probably getting confused here. So what I need exactly is the optimal set of actions on a poorly performing architecture which can lead to a much better architecture (the state S4 i was talking about). This would basically enable the user to directly make exactly those optimal changes in the actual hardware instead of trying every other possible architectural change and checking the performance.. If it is not necessary to model the MDP directly how can i choose the optimal policy? Are you pointing at model-free approaches here??
Comments.UserDisplayName: Bhavana
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-05T16:13:39.573Z
Comments.Text: Yes I am pointing at model-free approaches. You don't have an accurate model of the environment. You *could* learn a model from interactions with the environment, and that appears to be the way you are thinking. But there is no need, and I don't think it helps any in this case. I will answer the question anyway (no need to edit or delete) as it is interesting and I can point out a couple of details.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><rewards><policies><markov-decision-process>
Title: Can someone please help me validate my MDP?
UserDisplayName: Bhavana
ThreadText: # Can someone please help me validate my MDP?
  
  (Asked by: username_0 on 2019-09-05)
  
  **Problem Statement :**
  I have a system with four states - S1 through S4 where S1 is the beginning state and S4 is the end/terminal state. The next state is always better than the previous state i.e if the agent is at S2, it is in a slightly more desirable state than S1 and so on with S4 being the most desirable i.e terminal state. We have two different actions which can be performed on any of these states without restrictions.
  Our goal is to make the agent reach state S4 from S1 in the most optimal way i.e the route with maximum reward (or minimum cost). The model i have is a pretty uncertain one so i am guessing the agent must initially be given a lot of experience to make any sense of the environment. The MDP i have designed is shown below :
  
  **MDP Formulation :**
  [![MDP for the problem](https://i.sstatic.net/GuymJ.jpg)](https://i.sstatic.net/GuymJ.jpg)
  
  The MDP might a look a bit messy and complicated but it basically is just showing that any action (A1 or A2) can be taken at any state (except the terminal state S4). The probability with which the transition takes place from one state to the other and the associated rewards are given below.
  
  **States :** States S1 to S4. S4 is terminal state and S1 is the beginning state. S2 is a better state than S1 and S3 is a better state than S1 or S2 and S4 is the final state we expect the agent to end up in.
  
  **Actions :** Available actions are A1 and A2 which can be taken at any state (except of course the terminal state S4).
  
  **State Transition Probability Matrix :** One action taken at a particular state S can lead to any of the other available states. For ex. taking action A1 on S1 can lead the agent to S1 itself or S2 or S3 or even directly S4. Same goes for A2. So i have assumed an equal probability of 25% or 0.25 as the state transition probability. The state transition probability matrix is the same for actions A1 and A2. I have just mentioned it for one action but it is the same for the other action too. Below is the matrix I created -
  [![State transition probability matrix for both the actions](https://i.sstatic.net/lfyOS.jpg)](https://i.sstatic.net/lfyOS.jpg)
  
  **Reward Matrix :** The reward function i have considered is a function of the action, current state and future state - R(A,S,S'). The desired route must go from S1 to S4. I have awarded positive rewards for actions that take the agent from S1 to S2 or S1 to S3 or S1 to S4 and similarly for states S2 and S3. A larger reward is given when the agent moves more than one step i.e S1 to S3 or S1 to S4. What is not desired is when the agent gets back to a previous state because of a action. So i have awarded negative rewards when the state goes back to a previous state. The reward matrix currently is the same for both the actions (meaning both A1 and A2 have same importance but it can be altered if A1/A2 is preferred over the other). Following is the reward matrix i created (same matrix for both the actions) -
  
  [![Reward matrix R(A,S,S') for both the actions](https://i.sstatic.net/9HX88.jpg)](https://i.sstatic.net/9HX88.jpg)
  
  **Policy, Value Functions and moving forward :**
  Now that i have defined my states, actions, rewards, transition probabilities the next step I guess i need to take is to find the optimal policy. I do not have an optimal value function or policy. From lot of googling i did, I am guessing i should start with a random policy i.e both actions have equal probability of being taken at any given state -> compute the value function for each state -> compute the value functions iteratively until they converge -> then find the optimal policy from the optimal value functions.
  
  I am totally new to RL and all the above knowledge is from whatever i have gathered reading online. Can someone please validate my solution and MDP if I am going the right way? If the MDP i created will work ?
  Apologies for such a big write-up but i just wanted to clearly depict my problem statement and solution. If the MDP is ok then can someone also help me with how can the value function iteratively converge to an optimal value? I have seen lot of examples which are deterministic but none for stochastic/random processes like mine.
  
  Any help/pointers on this would be greatly appreciated.
  Thank you in advance
  
  **Tags:** reinforcement-learning, rewards, policies, markov-decision-process
  > **Comments:**
  > **username_1**: As defined there is no difference at all between the actions, and there is nothing to optimise (the agent will get the same expected reward regardless of what it does). However, you say this might change. On what basis will it change? Is this a toy problem to help you understand how optimising MDPs should work, so you can make arbitrary changes to help you learn? Or is it representing something real that you want to optimise?  
  > **username_0**: Would you suggest I have different reward function for both the actions?  
  > **username_1**: Your transition matrix says that the actions have no influence at all on the state transition, or on the reward. Probably I can base an answer on that. Also you cannot have "Another A2" The name A2 needs to fully specify the action taken. If there are choices to make *inside* the action, then that needs to be part of the MDP explicitly  
  > **username_0**: Well what i assumed was the state transition probabilities would be learnt by the agent. Initially an action on a state can lead to any of the other states. Unless until the agent/simulator is run with that action we wouldnt know which state it would land up in.  
  > **username_0**: What does this mean - If there are choices to make inside the action ?  
  > **username_1**: Oh right, so the state transitions are not the real state transitions - you have a "real" system with unknonws that you want an agent to learn? You don't need an explicit MDP model for the agent to learn optimal behaviour. But you might if you want to run a simulator of the environment to test an agent then of course you need to define something . . . it doesn't need to be a full MDP model, but that is OK, and might be instructive.  
  > **username_1**: "What does this mean - If there are choices to make inside the action ?". You said "Another A2" - what is different between the two A2 actions that you are thinking of?  
  > **username_0**: Right these are not real state transitions. But I would like the agent to learn and find out what the exact transitions are. So until then I assume it to be equal probability because I don't know which action on which action might lead to which state.  So what do you suggest how can I approach this problem ??  
  > **username_1**: Bhavana: OK, that makes more sense - you are talking about model learning, and assuming that RL needs to learn the underlying model. It can do, but much RL does not do this. For instance, Q Learning does not learn the MDP model. Do you actually want the agent to learn an accurate MDP model? I think I can answer your question as phrased here (and may do so later), but you should bear in mind that it may be leading you in the wrong direction, and that if what you want to do is learn an optimal policy for your microcontroller, it is not necessary to model the MDP directly  
  > **username_0**: Oh!! I am sorry I am probably getting confused here. So what I need exactly is the optimal set of actions on a poorly performing architecture which can lead to a much better architecture (the state S4 i was talking about). This would basically enable the user to directly make exactly those optimal changes in the actual hardware instead of trying every other possible architectural change and checking the performance.. If it is not necessary to model the MDP directly how can i choose the optimal policy? Are you pointing at model-free approaches here??  
  > **username_1**: Yes I am pointing at model-free approaches. You don't have an accurate model of the environment. You *could* learn a model from interactions with the environment, and that appears to be the way you are thinking. But there is no need, and I don't think it helps any in this case. I will answer the question anyway (no need to edit or delete) as it is interesting and I can point out a couple of details.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-09-05. Score: 2 | Accepted answer
  
  The good news is that:
  
  * Your MDP appears valid, with well-defined states, actions. It has state transition and reward functions (which you have implemented as matrices). There is nothing else to add, it's a full MDP.
  * You could use this MDP to evaluate a policy, using a variety of reinforcement learning (RL) methods suitable for finite discrete MDPS. For instance, Dynamic Programming could be used, or Monte Carlo or SARSA.
  * You could use this MDP to find an optimal policy for the environment it represents, again using a variety of RL methods, such as Value Iteration, Monte Carlo Control, SARSA or Q-Learning.
  
  The bad news is that:
  
  * All policies in the MDP as defined are optimal, with expected returns (total reward summed until end of episode) of $v(S1) = 55, v(S2) = 33.75, v(S3) = 21.25$ - solved using Dynamic Programming in case you are wondering.
  * The MDP is degenerate because action choice has no impact on either state transition or reward. It is effectively a [Markov Reward Process](https://en.wikipedia.org/wiki/Markov_reward_model) (MRP) because the agent policy has been made irrelevant.
  * Without discounting, the best result is not going from S1-S4 directly, as you appear to want, but repeatedly looping S1-S3-S2-S1-S3-S2... (this is currently hiiden by action choice being irrelevant).
  
    + There are a few ways to fix this, but maybe the simplest is to make the rewards more straightforward (e.g. +0, +10, +20, +30 for S1-S1, S1-S2..., -10, 0, +10, +20 for S2-S1, S2-S2...) and add a discount factor, often labelled $\gamma$, when calculating values. A discount factor makes immediate rewards have higher value to the agent, so it will prefer to get a larger reward all at once and end the episode than loop around before finishing.
  
  This whole "bad news" section should not worry you too much though. Instead it points to a different issue. The key point is here:
  
  > The model i have is a pretty uncertain one so i am guessing the agent must initially be given a lot of experience to make any sense of the environment.
  
  It looks like you have assumed that you need to explicitly build a MDP model of your environment in order to progress with your problem. So you are providing an inaccurate model, and expect that RL works with that, improving it as part of searching for an optimal policy.
  
  There are a few different approaches you could take in order to learn a model. In this case as your number of states and actions are very low, then you could do it like this:
  
  * Create a 2D tensor (i.e. just a matrix) to count number of times each state, action pair is visited, initialised with all zeroes, and indexed using S, A
  * Create a 3D tensor to count number of times each state transition is observed, again initialised with all zeroes, indexed using S, A, S'.
  * Run a large number of iterations with the real environment, choosing actions at random, and adding +1 to each visited S, A pair in the first tensor, and +1 to each S, A, S' triple in the second tensor.
  * You now have an approximate transition function based on real experience, without needing an initial guess, or anything particularly clever, you are just taking averages in a table. Divide each count of S, A, S' by the total count of S, A to get conditional transition probability $p(s'|s,a)$. It's not really an established, named RL method, but will do.
  
  However, if your construction of the MDP is just step 1 for running some RL policy optimisation approach, none of that is really necessary. Instead, you can use a model-free approach such as [tabular Q learning](https://www.learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/) to learn directly online from interactions with the environment. This is likely to be more efficient than learning the model first or alongside the policy optimisation. You don't need the explicit MDP model at all, and adding one can make things more complex - in your case for no real gain.
  
  You probably do still need to define a reward function in your case as there is no inherent reward in the system. You want the agent to reach state S4 as quickly as possible, so you need to monitor the states observed and add a reward signal that is appropriate for this goal. As above, I suggest you modify your planned reward structure to be simple/linear and add discounting to capture the requirement to "increase" state as fast as possible (here I am assuming that being in S2 is still somehow better than being in S1 - if that's not the case, and reaching S4 is the only real goal, then you could simplify further). That's because if you make the rewards for state progression non-linear - as in your example - the agent may find loops that exploit the shape of the reward function and not work to progress states towards S4 as you want.
  
  Beyond this very simple looking environment, there are use cases for systems that learn transition models alongside optimal policies. Whether or not to use them will depend on other qualities of your environment, such as how cheap/fast it is to get real experience of the environment. Using a learned model can help by doing more optimisation with the same raw data, using it to simulate and plan in between taking real actions. However, if the real environment data is very easy to collect, then there may be no point to that.
  
  > **Comments:**
  > **username_0**: Wow ! I cannot thank you enough for such a descriptive answer and explaining where I am going wrong. Things are pretty clear now .. Except one question in tabular Q-learning method you suggested. They have explained the reward and Q tables as a function of (state,action). For my problem i will have to consider the next state as well (ex. since S2 to S1 cannot be given same reward). Can i use the same concept explained there except I change the reward and Q tables to be functions of (current state,next state,action)? Then # of those tables == #actions for reward and Q tables.  
  > **username_0**: The format will be same as the reward table i have mentioned with current states in rows and next states in columns. Just that this will get complicated if i want to add more actions .. But would this way work ?  
  > **username_1**: You can change the reward function to match your problem, and it can depend on s,a,s' and also be stochastic, so you are fine with your proposed change. The Q table must be a function of state, action only, to match Q(s,a). You don't *define* that at the start- it is what the agent learns. It will correctly figure out the _expected_ stats, which is what it is for, so don't worry about adding s' to Q.  
  
  ---
  
  