# Is deep learning appropriate to approximate dynamic programming problems?

I have a problem which can be completely solved using dynamic programming, but in a very intractable way (On^4, where n is around 1000). I won't get into the details of the problem since it's a bit complicated, but it involves comparing properties of subsequences of a single string, where the property of subsequence (xi... xj) is related in a complex way to the property of subsequence (xi... xj + 1). I am fine with getting an approximation of the correct answer, but obviously would like to maximize correctness and minimize compute.

I have a well-defined metric for how good an answer is, but I have no idea what approach I should be using to solve it. I was thinking about turning it into a reinforcement learning problem for a deep neural network, as a way of avoiding having to find the best algorithm myself. I realized that I have no intuition for the kind of "algorithmic" problems for which deep reinforcement learning fits well. For instance, playing Go well was considered an "algorithmic" problem and has been advanced by using deep reinforcement learning, but the fact that it is nontrivial to teach multiply makes me think that certain seemingly simple problems might be out of reach. Is there a good way to think about what problems are well suited for deep reinforcement learning?

• As a general comment, even if $f(x_i \ldots x_j)$ is related in a complex way to $f(x_i \ldots x_{j+1})$, the fact that they are related suggests that there is some kind of locality. So without knowing anything about the problem, I wouldn't rule out the more well-understood class of Monte Carlo algorithms (e.g. Metropolis-Hastings, simulated annealing, evolutionary algorithms, etc). – Pseudonym Jul 29 '18 at 23:45