  The Markov assumption (MA) is fundamental to the empirical validity of
reinforcement learning. In this paper, we propose a novel Forward-Backward
Learning procedure to test MA in sequential decision making. The proposed test
does not assume any parametric form on the joint distribution of the observed
data and plays an important role for identifying the optimal policy in
high-order Markov decision processes and partially observable MDPs. We apply
our test to both synthetic datasets and a real data example from mobile health
studies to illustrate its usefulness.
