Are RNNs Markovian?

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.

• Markov are defined by randomness, so RNNs can't be unless it makes a random manipulation on each layer. For deterministic manipulations on a layer there is however room for an analogy. Markov processess have a memory effect too, since the occurence of current state depends on the random events at each state in the past. What is random is not the current state, but the step it takes to the next state. . – ReneBt Jun 12 at 8:16
• If you're applying RNN to extraction of meaning from speech then it can't be Markovian. You can't possibly argue that what I say right now is independent of what I said before. I am the factor that persist and what I'm going to say in future clearly depends not only on my state right now but on every second of my existence – Aksakal Jun 12 at 20:02
• @ReneBt I'm not quite sure how determinism or randomness is relevant since a probability distribution can be generated deterministically at any given state given the previous step, e.g., a simple unitary rotation of the probability weights could be all that the RNN cell does. – Tfovid Jun 13 at 10:33
• @Aksakal Sure, but this does not preclude the fact that, in some latent representation of what "you say right now", there does not exist a summary of what "you said before"---which, if I'm not mistaken, is how RNNs work. – Tfovid Jun 13 at 10:45
• @Tfovid, right, RNN can assume that the process is Markovian, and it probably should if it wants any success. I'm saying the DGP itself cannot be Markovian generally. Suppose, you listen to a comedian making awful jokes, unless you know the context and the comedian it would be impossible to devise what's meant. Or a testimony in the court - lawyers pay a lot of attention to the "character" of the witness when assessing the witness statement, that's non Markovian – Aksakal Jun 13 at 15:26

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).

• I understand your argument in the context of reinforcement learning, although I can't quite picture where RNNs fit in the typical (RL) problem. (The only deep learning scheme applied to RL that I know of is deep Q learning, but those are not RNNs anyways). I made an edit to my question to better qualify the problem I had in mind. To me, RNNs seem very much Markovian. The states $s_t$ in your answer are the hidden layers of the RNN and once a given $s_t$ is reached, all states before it become irrelevant since they've somehow "collapsed" the history to give rise to $s_t$. Am I mistaken? – Tfovid Jun 13 at 11:09
• According to my knowledge, RNNs were explicitly designed to solve the vanishing gradient problem which is a common one in RL: To base the current decision also on things that happened long ago in the past rather than only on the short-time memory... So the relationship between RNNs and RL is quite tight (input: current state and the last hidden state, output=action distribution and next hidden state)... why do you think that they are not in relationship? As I said: the input for the current call at $t$ is $h_{t-1}$ which depends on all the past... so it is absolutely not Markovian... – Fabian Werner Jun 15 at 9:58