chose to make a guess (i.e., $a=d+1$), the state remains unchanged and the episode terminates.

-   Reward function: For any question action ($1 \le a \le d$), the reward is a small random number: $\mathcal{R}(s, a) = 0.1 \cdot \mbox{Unif}(0,1)$. For a guess action (i.e., $a = d+1$), the reward corresponds to the probability the environment guesser $G$ assigns to the true label, $\mathcal{R}(s, d+1) = \mbox{Prob}(G(s) = y)$. Observe that the fact that the reward function is parametrized by the guesser network, which is trained as well along with the agent, makes the MDP non-stationary, as during the course of training the guesser’s weights change and correspondingly so does the reward function. This non-stationarity of the MDP deviates from the majority of recent RL works, which consider a stationary setting. To cope with the challenges the non-stationary setting introduces, we alternate between training of the guesser and of the agent, as will be explained in Section \[sec:add\].

### The Environment {#sec:env}

As mentioned above, we augment our environment with a Guesser network, which is trained along with the RL agent. The guesser $G$ maps a state $s$ to $G(s)$, which is the probability assigned by the guesser to a 