Is deep learning appropriate to approximate dynamic programming problems?

Question

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 (x_i... x_j) is related in a complex way to the property of subsequence (x_i... x_{j + 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?

Answer 1

A good start would be to understand what reinforcement learning is; and identify which problems are reinforcement learning problems and which aren't. Deep reinforcement learning is only relevant if you have a reinforcement learning problem; otherwise, it's almost certainly not relevant. Among other things, reinforcement learning deals with a stateful system. You don't seem to have a stateful system so it's not clear to me why you think reinforcement learning would be relevant.

Since you haven't told us what the problem is, it's hard to imagine how we can tell you how to solve it; all I can share is general principles. In general, deep reinforcement learning isn't magic that you use whenever a problem is too hard for normal methods; it is useful for a specific purpose, and I don't see any reason to expect it to be effective or applicable here.