I recently just started learning reinforcement learning and learned that reinforcement learning algorithms work under the assumption of MDP or POMDP. However as I read A3C and recent vision based deep RL papers, it seems some of them aren't assuming MDPs but used RNNs or LSTM to make it seem as if it is MDP.

So my question is: how does reinforcement learning algorithms work without the assumption of (PO)MDPs?

  • $\begingroup$ Could you clarify what you mean by "modeled"? Theoretical results and guarantees may depend on assuming an MDP (or not), but many RL algorithms do not explicitly model the environment. It not really clear from the question whether you are asking about this aspect (explicitly modelling an environment as an MDP or not) or something more theoretical (can the environment be represented as an MDP in principle, and is that necessary, regardless of whether a model is being created)? $\endgroup$ – Neil Slater Sep 18 '18 at 16:39
  • $\begingroup$ Sorry, I may have used the wrong word. Probably the word "assume" makes more sense here. What I meant to say is: How can RL algorithms such as A3C-LSTM work without assuming MDP? I thought policy gradient methods work since it assumes MDP. $\endgroup$ – haruishi Sep 18 '18 at 16:53

How does reinforcement learning algorithms work without the assumption of (PO)MDPs?

It doesn't. The theory of reinforcement learning is tied very strongly to an underlying MDP framework. The RNN-based solutions that you are referring to are fully compatible with such an MDP model, and don't even require a POMPDP to be useful.

Without the core guarantees of a (PO)MDP model, or something closely equivalent, it is not clear that any learning could occur, with any kind of agent. The MDP model of an environment is about describing consistent behaviour, that is predictable to some degree, and random/stochastic otherwise, and the predictable parts make it amenable to at least some optimisation. The split into states, actions, time steps and rewards help organise the thinking around this. They are not necessary for other kinds of policy-search approaches, such as genetic algorithms. However, if you try to break away from something that would fit to a (PO)MDP, it would break any other kind of meaningful policy too:

  • If actions had no consequence, then you could learn the value of being in a particular state, but you could not optimise an agent. This could be modelled as a Markov Reward Process, provided state transitions were not completely random, otherwise just learning associations of state to reward using a supervised learning approach would be the best you could do.

  • If rewards were not consistently based on any data available to the agent, not even history, but not random, then there is no way to learn how to predict or optimise rewards.

  • Similarly for state transitions, if they bear no relation to any information known about the environment, current state or history, but are not random, then there is no way to learn about the non-randomness, and no kind of agent could generate a meaningful policy to take advantage of knowledge about the system, because the knowledge available is not relevant. However, if the current state still influenced what rewards were available to which actions, then a contextual bandit approach might work (plus a supervised learning approach could predict currently available rewards).

When the information about rewards or state transitions is not directly available, but can be inferred or guessed at least partially from history or context, then you can model this as a POMDP.

One common scenario you can face is that you have available some observations about the environment, but are not sure how to construct a state description that has the Markov property. The velocity of an object might be such a detail, when your observations only give you positions. Technically a POMDP and this observation/state mismatch are the same basic issue, if you decided arbitrarily that your observation was the state.

When faced with this mismatch between easily-available observations and a state description based on history that would be more useful, you can either try to engineer useful features, or you can turn to learning models that will infer them. That is where using RNNs can come in useful as part of RL, and they can help with both observation to state mapping and also inferring more complex hidden state variables in POMDPs. Use of hidden markov models to model a "belief state" that augments the observed state is similar to the latter use of RNNs.

  • $\begingroup$ Thanks for the detailed explanation! The neural network does the job of learning the hidden state variables in POMDPs, so you don't have to engineer it yourself. $\endgroup$ – haruishi Sep 19 '18 at 6:18

Your Answer

