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 &quot;modes&quot;).  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 &quot;naive&quot; 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:

The states are the different values of $x$
The actions are $u_1,\dots,u_L$
The transition is given by $f$
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