How should I define an MDP for this problem where we need to guess a number and minimise the number of guesses?

Question

A number has randomly been chosen from 1 to 3. On each step, we can make a guess and we will be told if our guess is equal, bigger or smaller than the chosen number. We're trying to find the number with the least number of guesses.

I need to draw the MDP model for this question with 7 states, but I don't know how the states are supposed to be defined. Can anyone help?

Answer 1

When formulating a problem into an MDP, you need to define the states, of the system, the possible actions you can take, the transition probabilities between states depending on the action, and the rewards earned (or costs paid) for the state transitions. The important part here is to create a state-space that has a Markov property which in plain words means that in any given state you have enough information to make the optimal decision.

• Rewards: in this case, I think it is fairly obvious that a positive reward should be given if we find out the number and zero reward if we don't.

• Actions: the action we can take is making a guess, that is the possible actions will come from the action-space A=(1,2,3).

• States: this is a bit more difficult to come up with. Here the intuition should come from thinking about the actions you can make and how they change the information you have about the system. In our state-space, each state will represent the set of numbers that the answer might possibly be. For example in a state, the (1,3) we know that the guessed number is either 1 or 3. Also, we will denote these states with capital letters to simplify the state transitions.

  • A=(1, 2, 3): the initial state as at the beginning of the search the guessed number can be either of 1, 2 or 3;
  • B=(1, 2): the guessed number is either 1 or 2;
  • C=(1, 3): the guessed number is either 1 or 3;
  • D=(2, 3): the guessed number is either 2 or 3;
  • E=(1): the guessed number can only be 1;
  • F=(2): the guessed number can only be 2;
  • G=(3): the guessed number can only be 3;
  • H=(): final state, we found the guessed number.

• State transitions: this is very simple, just imagine which states are reachable in a state depending on the guess (action) we make. Here the notation P(A|B,1) will mean the probability that we reach state A from state B given that we guessed 1. (Note: we will assume uniform distribution for the guessed number). I think I'll be lazy here and not write down all the transitions as they get very repetitive once you understand how they are made, I'll just provide examples for all cases.

  • P(D|A,1)=2/3: we guess 1 in the initial state and we miss with 2/3 chance, the reply will be that the guessed number is greater than 1.
  • P(H|A,1)=1/3: we guessed right, so we reach the final state.
  • P(B|A,3)=2/3: similarly we guess 3 and miss.
  • P(H|A,3)=1/3: we guess 3 and we are right.
  • P(C|A,2)=0: if our guess 2 is wrong we get a reply of whether the guessed number is greater or smaller than 2 therefore we won't get into this state.
  • P(E|A,2)=1/3: we guess 2 and the reply is that the number is smaller than 2.
  • P(G|A,2)=1/3
  • P(H|A,2)=1/3
  • P(B|B,3)=1: guessing 3 in state B doesn't provide more information so we reach the same state with probability 1.
  • P(H|B,1)=1/2: 1 is the right guess with 1/2 probability in this state.
  • P(F|B,1)=1/2: similarly we miss with 1/2 chance if we guess 1 so we reach state F where we know what is the good solution however we haven't won yet as we still need to make one more guess to reach the final state.
  • P(F|F,1)=1: again guessing 1 in state F doesn't give us extra information so we get back to state F.
  • P(H|F,2)=1: however, guessing 2 in state F will give us the final state, as it is the right guess.

Note that I defined 8 states earlier, however, state C=(1,3) is never reached so we don't actually need it.

I hope this helped and you will be able to finish the rest.