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 :
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 -
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) -
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