If the Markov assumption is wrong, will a learner still converge to a stable policy?

Question

I'm trying to figure out what guarantees can be made if a learner wrongly assumes a problem obeys the Markov transition property. Assume I have a problem defined by a partially observable Markov decision process (POMDP):

$(S,A,T,R,O)$

Where $S$ is the set of possible states, $A$ the set of possible actions, $R$ is the reward function, $O$ is a set of conditional observation probabilities, and $T : S \times A \times S \rightarrow [0,1]$ a transition function obeying the Markov transition property:

$P(s_t | s_{t-1}, a_{t - 1},\dots, s_0, a_0) = P(s_t | s_{t-1}, a_{t-1}) $

Further, lets assume the set of states $S$ is defined by joint assignments to the variables $X_1, \dots X_n, H$, and the observations are just the states projected over the observable $X_i$ variables (so, if the current state is $(x_1, \dots, x_n, h)$ the observation would be $(x_1, \dots, x_n)$)

What if a learning agent didn't know that the problem was a POMDP, wasn't aware $H$ existed, and instead thought the problem was a fully observable Markov decision process with states given by assignments to $X_1, \dots, X_n$?

If the learner tries to learn the optimal policy $\pi^*$ in a model-based way (e.g, by trying to learn the transition function based on trials produced via an $\epsilon$-greedy strategy, then computing the optimal policy via e.g., value iteration), can anything be said about how that learner would perform?

Obviously, there is no guarantee whatsoever that it will learn $\pi*$---without acknowledging $H$ exists, the problem is not necessarily Markov, so the learner is trying to learn a stationary transition function $P(s'| s, a)$ which might in fact be dependent on the current time $t$. I'm wondering however if, as $t \rightarrow \infty$, the learner's policy $\pi_t$ will converge at all. In other words, will the learner eventually stick to some policy $\hat{\pi}$ it believes to be "best", or is there a chance it will fluctuate between several different policies forever?

Answer 1

What about an environment with one state and two actions, left and right. left gives 1 reward while right gives -1 reward, but every 1 million steps, this reverses so right gives 1 reward and left gives -1 (and then flips again at 2 million so that left is the best action again). This is of course possible in a POMPD if there is a hidden variable counting the number of steps which have passed.

It seems like value iteration would very quickly converge on always picking left, only to end up changing strategies every 1 million steps forever. This depends heavily on exactly how your model learning works, but I assumed that you would just have an online linear model which maps $s,a,s'$ to reward. (actually even if you fit your model on all the data, you could flip the environment at 0.5, 1.5, 2.5, etc million steps, and it would oscillate between predicting left is a slightly better action and right is a slightly better action)

As for conditions under which convergence can be guaranteed: if you fit your transition / reward model only after collecting a huge amount of data -- so that the POMPDP has reached some steady-state distribution, then value iteration must converge.