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?

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?

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:

$(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 MDP 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?

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?

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:

$(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 MDP with states given by assignments to $X_1, \dots, X_n$?

If the learner tries to learn the optimal policy 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 value iteration), can anything be said about how that learner would perform?

Obviously, there is no guarantee whatsoever that it will learn the optimal policy---without acknowledging the existence of $H$, the problem is not necessarily markov, so the learner is trying to learn a stationary transition function which might in fact be dependent on the current time. I'm wondering however if, in the limit, the learner's policy will converge at all. In other words, will there be some number of trials after which the learner will eventually stick to some policy it believes to be "best", or is there a chance it will forever fluctuate between a set of different policies?

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:

$(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 MDP 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?