What?

A way to add additional edges to a graph based on the downstream task performance as well as a bunch of interesting connections between different areas of research (Finite State Automata, POMDPs and Successor Representations).

Why?

It's not straightforward, how to construct a graph from some relational data (Yes! And sometimes, the default approach can be suboptimal). Automation is good, let's automate this. Pun intended!

How?

source: original paper

Main idea:

• Take an existing graph (e.g. abstract syntax tree of a program or a maze grid).
• Put an RL agent on a graph node and define the action space:
  • Move to other nodes
  • AddEdgeAndStop (add an edge from the initial node $n_0$ to the current node and stop the episode)
  • Stop an episode without adding the edge.
  • Reset the episode.
• Let the agent run.
• Average the trajectories to get the expected adjacency matrix.
• Use the resulting graph for the downstream task.

<aside> 💡 We would like our agent to be powerful enough to extract useful information from this POMDP, but simple enough that we can efficiently compute and differentiate through the learned trajectories.

</aside>

Since the authors care about program analysis and regular languages, they use finite-state automata.

To get the adjacency matrix, we need to compute the probabilities of each of the final action $a_T$ in final node $n_T$:

$$ p(a_T, n_T|n_0, \pi_\theta) = \big[\sum_{i\geq0}{HQ^i_{n_0}\delta_{n_0}}\big]{(a_T, n_T)} = H{(a_T, n_T), :}(I-Q_{n_0})^{-1}\delta_{n_0}, $$