  Learning directed acyclic graph (DAG) that describes the causality of
observed data is a very challenging but important task. Due to the limited
quantity and quality of observed data, and non-identifiability of causal graph,
it is almost impossible to infer a single precise DAG. Some methods approximate
the posterior distribution of DAGs to explore the DAG space via Markov chain
Monte Carlo (MCMC), but the DAG space is over the nature of super-exponential
growth, accurately characterizing the whole distribution over DAGs is very
intractable. In this paper, we propose {Reinforcement Causal Structure Learning
on Order Graph} (RCL-OG) that uses order graph instead of MCMC to model
different DAG topological orderings and to reduce the problem size. RCL-OG
first defines reinforcement learning with a new reward mechanism to approximate
the posterior distribution of orderings in an efficacy way, and uses deep
Q-learning to update and transfer rewards between nodes. Next, it obtains the
probability transition model of nodes on order graph, and computes the
posterior probability of different orderings. In this way, we can sample on
this model to obtain the ordering with high probability. Experiments on
synthetic and benchmark datasets show that RCL-OG provides accurate posterior
probability approximation and achieves better results than competitive causal
discovery algorithms.
