Assume you are given a sequence of states followed by the agent, generated by a random policy, $[s_0, s_1, s_2, \dots, s_n]$. Furthermore, assume the MDP is fully observable and time is discrete.

Is it possible to find the Q-value for a state-action pair $(s_j, a_j)$ which was not encountered along this sequence?

From my understanding of the MDP, yes, it would be possible. However, I'm unsure how to get this Q-value.


My understanding from your question is that you have the following data generated from a random policy:

$$[s_0, s_1, s_2 . . . s_n]$$

That is, the state observed at each time step.

You know nothing more about the MDP, such as the transition or reward functions. Although the MDP is discrete and fully observable (and thus usual RL theory is supported), you do not have any observations other than a single list of states.

You wish to obtain an estimate for $Q(s_j, a_j)$, given a specific state/action pair that has not been observed before. This is not possible. You do not have any data from your observations regarding rewards, nor the actions taken by the random agent. At minimum, you would need data about rewards and actions that were observed. Observed rewards are needed to calculate returns, and value functions are expected returns. Observed actions are needed to assign returns to the correct $(s,a)$ pair when calculating estimates.

In addition, if you want to make a meaningful estimate for an as-yet unseen state/action pair, then you would need to be using some form of function approximation for the action value function Q. Otherwise your estimate will be whatever default estimate you had assigned at the beginning of learning.

What inferences can you make given the data you have? Very roughly:

$$p(s_{k+1} | s_k, \pi ) \gt 0, \forall k \in [0,n-1]$$

i.e. the state sequence that was observed gives you proof of non-zero transition probabilities between those states under the given policy. This is not enough to learn a value function, but might have other uses.

With repeated observations - multiple lists of observed states - you could infer what those probabilities were, but would not be able to separate the effect of action choice from state transition rules (because the action was not observed). If you added reward observations then you could learn a state value function.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.