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?
