2
$\begingroup$

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?

$\endgroup$

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.