# reference request: solving problems by dynamic programming + quantization to avoid combinatorial explosion

The context: I have been working lately with problems like the following: Let $$x_{k}\in\mathbb{R}^n$$ be a state evolving accroding to: $$x_{k+1} = f(x_k,u_k), k=0,\dots,N-1$$ given some $$x_0$$ and controls $$u_0,\dots,u_{N-1}\in\{1,\dots,L\}$$ (the set of possible controls is a finite set of "modes"). The goal is to choose the controls to minimize $$J = \sum_{k=0}^{N} g(x_k)$$ In most of my examples, $$f$$ does provide structure to make $$x_k$$ lie in a finite set, but may lie an arbitrary place in $$\mathbb{R}^n$$ in general. The "naive" solution would be to make a tree traversing all combinations of $$u_0,\dots,u_{N-1}$$, then look for the leaf with the least value of $$J$$. Of course, branch and bound or other techniques may be used, but as far as I know this approach won't be able to get rid of the exponential complexity $$O(L^N)$$ (right?).

In order to provide structure to the state space, I decided to quantize $$\mathbb{R}^n$$ in blocks of length, say $$\epsilon$$, and assume that $$x_k$$ won't exit a box $$[-B,B]^n\subset\mathbb{R}^n$$, so that $$x_k$$ will always lie in a set of finite size $$\mathcal{X}\subset\mathbb{R}^n$$ and $$\hat{f}:\mathcal{X}\times\{1,\dots,L\}\to\mathcal{X}$$ is the approximation of $$f$$ in this setting. In this context, since $$\hat{f}$$ transitions between finite sets, one can build a trellis diagram of $$N$$ stages with weights given by costs $$g(x_k)$$, then we may apply a shortest path algorithm (viterbi-like approach) which is polynomial. (right?).

To formalize this approach I plan to:

• Use the original $$f$$ to obtain a bound $$B$$ which will depend on $$N$$.
• Show that for a correct value of $$B$$, one obtains that the true optimum $$J^*$$ and our approximated one $$J_\epsilon$$ comply that $$J_\epsilon\to J^*$$ as $$\epsilon\to 0$$.

My questions:

• I have read that in other problems, a similar quantization approach have been used to obtain a trade-off between accuracy and computational complexity, e.g. in some knapsack problem solutions or some scheduling problems, although these methods quantize the cost and not the state space. My question is, if this approach (quantization + dynamic programming) is standard, if it has a name and if there is a standard reference for me to read more about it.
• Given the problem statement I gave, do you think the solution outline I provided is suitable, or if there is a different approach you can suggest?

This sounds like a reinforcement learning problem.

Construct the following MDP:

1. The states are the different values of $$x$$
2. The actions are $$u_1,\dots,u_L$$
3. The transition is given by $$f$$
4. The reward is given by $$g$$ of the current state.

Define it as a finite horizon problem.

Then, if the set of the values of $$x$$ is finite, use any RL technique to solve the problem (you can use a dynamic programming solution from there to compute the exact solution).

If the state space is infinite, or extremely huge, consider trying to use the equivalent techniques from reinforcement learning.

If you wish, leave here a comment and when I will be able to I will send the algorithms themselves.

Anyways, from my understanding of your solution - it looks correct. But you need to be cautious about the use of $$B$$ and $$\epsilon$$ since cutting the space into boxes increases the number of boxes dramatically with the increase of the dimensions

• Very interesting! As far as I know, using RL doesn't provide any optimality guarantees, right? Is that what you mean by computing the exact solution? Can you elaborate on that part? (my advisor is particularly interested in performance bounds) Anyway, for cases with big $n$ I might take your advice and use RL. Thanks! – FeedbackLooper May 21 at 15:53
• RL does provide optimality guarantees, depending on the problem definition and algorithms used. For example, for the case of a finite small set of states and actions, if you are given the description of the MDP - you can use the policy iteration algorithm and after a finite number of steps (I don't remember the exact bound, but I think it was a linear bound) you are guaranteed to end up with the optimal policy. However, for cases with huge state space \ infinite state space, the convergence is not guaranteed (I don't know of proofs at least) but usually you will reach a local optimum. – nir shahar May 21 at 16:09
• Take a look here: incompleteideas.net/book/first/ebook/node43.html for explanation on the policy iteration algorithm – nir shahar May 21 at 16:10
• Oh! that is very useful to me. I will take a look at it. thanks, sir! – FeedbackLooper May 21 at 16:25