Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
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.
