Are RNNs Markovian?

Question

On the one hand, one can argue that they are since "the hidden layer is simply [derived from] the last hidden state and current input". On the other hand, the whole point of RNNs is that "their rich internal state allows them to keep track of long-distance dependencies", hence the non-Markovianity.

Which one is it?

EDIT: There were some questions as to which particular problem domain I was referring to, e.g., natural language processing, reinforcement learning, etc. Ideally, I'd like to keep the question as high-level and domain-agnostic as possible, but what I ultimately want to apply it to is as follows: I have a set labeled, attributed entities that interact over time. If it weren't for the interactions, a straightforward supervised learning on the attributes of the entities would allow for their classification. However, because of the interactions, which we can encapsulate as black boxes, the attributes change over time as they "influence" each other upon "contact". My aim is to model the black boxes. Presumably, the whole history of interactions that an entity undergoes should factor in its latest estimation of the label. However, if one collapses, i.e., aggregates, the history at each time step into a latent representation, then one can forget the past since it's supposed to have been encoded into the current state, hence my confusion as to whether the interaction black boxes I am trying to design behave in a Markovian or time-dependent manner, RNN-like recurrent cells.

Answer 1

In Reinforcement Learning (which is the domain I guess this question wants to look at) we are given a Markov decision automata (that very precisely spoken gives rise to infinitely many Markov Decision Processes that consist of random variables $A_t, S_t, R_t$) and we seek models $\pi$, i.e. functions $\pi:A \times S \to[0,1]$ that provide a 'good' distribution

$$p(a_t|s_t) = \pi(a_t|s_t)$$

such that a certain quantity (namely the infinite exponential sum over rewards) is being maximizes, i.e. we are looking for things that help us make decisions which action $a_t$ to take next given that we are currently in a state $s_t$ such that the long term reward is maximal.

I do not completely agree with @ReneBT: models such as RNNs can be seen as providing such a distribution over the action space given the past states, i.e. what they actually spit out is just numbers $y_{a}$ such that $\sum_{a} y_{a} = 1$ (the last layer is a softmax over the actions so that the probabilities of the actions sum up to one). The RNN itself does not really make a final decision on which action actually to use next (some people sample that from the action space according to this distribution, some people just take argmax, ...).

The question is: What does this distribution actually depend on? Technically, each call of the RNN unit receives the current input (state) $s_t$ and the hidden output of the call before $h_{t-1}$. However, the hidden state $h_{t-1}$ depends on $h_{t-2}$ and $s_{t-1}$ and so forth...

Hence, what they actually model is something like

$$p(a_t|s_t, s_{t-1}, s_{t-2}, ...)$$

and that is explicitly not Markovian because it depends on all the history instead of just the current and/or the current and the last state.

One should also remark that one can 'fix' models that only depend on a fixed past of states, i.e. if it looks like this

$$p(a_t|s_t, s_{t-1}, s_{t-2})$$

then one can reinterpret the state space as $S \times S \times S$ and then these models 'kinda' become Markovian (however, not in the original space!). As RNNs, however, depend on all the past $s_{t-1}, s_{t-2}, ..., s_0$ they cannot be fixed in that way. Theoretically they should be much stronger than Markovian models. However, from a purely theoretical point of view we do not really need these 'strong' models: Given that the state and action space satisfy some 'regularity conditions' (for example, they are both finite) then the best policy is a Markovian deterministic one (see Puterman: Markov Decision Processes and Discrete Stochastic Dynamic Programming, Thm. 6.2.10 on p. 154).

That is (I believe) the reason that everything is 'fair' again: We use something that is more powerful (i.e. we kinda cheat the setup) but we do not actually need to use it... It is just a helping tool in order to come closer to this -provably- best, discrete policy (in the same way that we are using probabilistic policies although we do only need to search through the space of deterministic ones... but this space is too big so we approximize by probabilistic ones).

Answer 2

Although you are asking if RNN is strictly markovian, I think you should rather ask can I build reinforcement learning for non-markovian process.

No one mentioned simple markov process definition - if next state depends only on current state - this is markov process. If that fails (and from what I gather - your states depends on multiple previous states) - your process is Non-Markovian. There are multiple articles on Non-Markovian reinforcement learning.

NMP RL paper