Can someone please help me validate my MDP?

Question

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 :

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

Answer 1

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 (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 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.