A Study of State Aliasing in Structured Prediction with RNNs
Figure 7: Number of times the model fails to learn the optimal policy on the sequential maze.
['Reward Function', 'Number of failures']
The optimal policy given reward function R1 is to output a sequence of items starting with left in x3, and then output a sequence of items starting with right in x2. In this case, the optimal actions in x1 and x2 are distinct: if the agent is in x1, it should output a sequence of tokens starting with left. Function R2 entails the same optimal policy but changes the optimal actions in x1 so that they correspond exactly to the optimal actions in x2. Finally, R3 is meant to test if state aliasing occurs when only the first token of the optimal actions is shared between x1 and x2. In this case, in x1, the agent should output right, right whereas in x2, it should output right, left. We train a simple sequence-to-sequence model with a GRU encoder that takes the 3-bit input and outputs a 3-dimensional hidden state. This state is used to initialize a GRU decoder, which takes as input the empty action (-1) at the initial time step and the previously produced token thereafter (0 for right, 1 for left). The decoder uses a 3-dimensional hidden state. We apply a linear transformation and then a softmax on this hidden state to output a probability distribution over the next action token. We train this model via REINFORCE without entropy-based exploration nor any baseline computation. Additional implementation details are provided in the Appendix. When the optimal actions are distinct (function R1), the encoder-decoder model only fails 5 times out of 50, which is similar to our observations in the single-token case. When the optimal actions are exactly the same in x1 and x2 (function R2), the model almost always fails to learn the optimal policy (92% of the time). In our experiments, whenever the model fails, it converges to the same suboptimal policy due to state aliasing – the hidden states of the encoder after visiting x1 and after visiting x2 are very close. Surprisingly, the model is subject to state aliasing even when only the first token of the optimal action is the same for x1 and x2 (function R3). The problem does not occur as often in this setting, but the model fails 30% of the time. The aliasing phenomenon appears clearly here and our analysis suggests it is responsible for a large number of failure cases when using R3.