I'm working on a sequential decision making problem and am looking at a constraint that I'm not sure how to deal with. We want to maximize the sum of a finite known sequence of bounded functions $F_{t}: U \rightarrow \mathbb{R}$. The decision variables $u_{t}$ are one-hot encoding vectors, $U = \left\{ u \in \{0, 1\}^{n} | \sum_{i} u_{i} = 1 \right\}$. A solution $u^{*}$ is a sequence of these one-hot vectors, but I am constrained in the number of times the one-hot vector changes in that sequence, i.e. $u_{t+1} \neq u_{t}$. Let $b$ be the constraint value. The optimization program looks like this:
$$ \begin{align} \text{maximize} & \,\,\, \sum_{t = 1}^{T} F_{t}(u_{t})\\ \text{subject to} & \,\,\, \sum_{t = 1}^{T-1} \frac{1}{2} || u_{t+1} - u_{t}||_{1} \leq b \end{align}$$
where $||\cdot||_{1}$ is the L1 norm. For some $t$ the constraint is $0$ if $u_{t+1} = u_{t}$ and $1$ otherwise. Most examples from dynamic programming I'm familiar with view budget constraints on the values of u_{t} and not the first differences in sequence. I'm uncertain as to how to unroll this problem starting at T-1 and working backwards in a dynamic programming fashion.
You can use Dynamic Programming, where the state is the current time, the budget used so far ($x$), and the last $u_t$. The recurrence relation is:
$$f(t, x, u_t) = F_t(u_t) + \max\{ f(t-1, x, u_t), f(t-1, x-1, 1-u_t) \}.$$