Consider a finite set of matrices $A_1,\dots,A_L\in\mathbb{R}^{n\times n}$ and a recurrence equation of the form: $$ x_{k+1} = A_{\sigma(k)}x_k $$ where $x_k\in\mathbb{R}^n$ is the state and $\sigma(k)\in\{1,\dots,L\}$. My goal is that given an initial condition $x_0$ and some fixed integer $N>0$, obtain a sequence or schedule $\sigma(0),\dots, \sigma(N-1)$ which maximizes $$ \left(\sum_{k=0}^{N-1}r(\sigma(k)) - \lambda\left(x_k^TQx_k\right)\right)-\lambda\left(x_N^TQx_N\right) $$ where $r:\{1,\dots,L\}\to\mathbb{R}_{\geq 0}$ is a function which outputs a reward depending on which value $1,\dots,L$ was used, $\lambda>0$ and $Q\in\mathbb{R}^{n\times n}$ is positive definite.
Up to now I have only been able to "solve" this problem by inspecting all $L^N$ possible sequences $\{\sigma(k)\}_{k=0}^{N-1}$. However, as you can see, this solution is not very efficient.
My question is if there is another way to solve this same problem with less computational complexity or if due to the combinatoric nature of this setting, we are tied up to an exponential complexity (in $N$)?
If we cannot get rid of the exponential complexity in $N$, do you think there is another approach to obtain at least an approximate solution worthy of exploring?