Given a list of $N$ questions. If question $i$ is answered correctly (given probability $p_i$), we receive reward $R_i$; if not the quiz terminates. Find the optimal order of questions to maximize expected reward. (Hint: Optimal policy has an "index form".)

I am fairly new to Reinforcement Learning and Markov Decision Problems (MDP). I am aware that the goal of the problem is to maximize the expected reward but I am not sure how exactly to formulate this into an MDP.

This is the approach I thought of:

1) Assume only 2 questions. Then the state space is $S\in \{1,2\}$.

2) Compute the expected total reward $J = E(R)$ for both cases, when we start with question $1$ and question $2$ and then find the maximum of the two.

3) If we start with $1$, then $$J(S_0 = 1) = p_1(1-p_{2})R_1 + (R_1 + R_2)p_1p_2$$

4) Similarly, if we start with $2$, $$J(S_0 = 2) = p_2(1-p_{1})R_2 + (R_1 + R_2)p_1p_2$$.

To determine the maximum reward of the two, the required condition for $1$ to be the optimal starting question is $$R_1p_1 - R_2p_2 + p_1p_2(R_2 - R_1) \gt 0$$ If the above expression is negative, then we should start with $2$.

I would like to know if the approach is correct and how to proceed further. I am also not sure how to define the action space in this case. Can a dynamic programming approach be used here to find the optimal policy?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.