# Resilience Analysis for Double Spending via Sequential Decision Optimization
## 5 Decisions under Uncertainty: Optimal Switching and Stopping
Furthermore, there are applications to pricing financial options [23], natural resource extraction [21], battery management [24] and optimal asset allocation under hidden state dynamics [25], many applications are illustrated using R in [26]. Let us now introduce the standard backward induction algorithm which is used to obtain a solution to an optimal switching problem. Given a switching problem as above, introduce the stochastic kernels for all \(p\in P\), \(a\in A,z\in\mathbb{R}^{d}\)  
\[\mathcal{K}_{t}^{a}v(p,z)=\mathbb{E}(v(\alpha(p,a),Z_{t+1})\,|\,Z_{t}=z), \qquad t=0,\ldots,T-1, \tag{10}\]  
which act on all functions \(v\) on \(E=P\times\mathbb{R}^{d}\) where the above expectation exists. Using these kernels, the policy value is obtained recursively by the _policy valuation_ algorithm  
\[v_{T}^{\pi}=r_{T},\quad v_{t}^{\pi}(p,z)=r_{t}(p,z,\pi_{t}(p,z))+\mathcal{K}_{ t}^{\pi_{t}(p,z)}v_{t+1}^{\pi}(p,z),\quad t=,T-1,\ldots 0.\]  
To obtain a policy \(\pi^{*}=(\pi_{t}^{*})_{t=0}^{T-1}\), which maximizes the total expected reward, one introduces for each \(t=0,\ldots,T-1\) the so-called _Bellman operator_  
\[\mathcal{T}_{t}v(p,z)=\max_{a\in A}\left(r_{t}(p,z,a)+\mathcal{K}_{t}^{a}v(p, z)\right),\quad(p,z)\in E \tag{11}\]  
acting on each function \(v:E\to\mathbb{R}\) where the above expectation exists. Now, consider the _Bellman recursion_, also referred to as the _backward induction_:  
\[v_{T}=r_{T},\quad v_{t}=\mathcal{T}_{t}v_{t+1},\qquad\text{for }t=T-1,\ldots,0. \tag{12}\]  
Under appropriate assumptions, there exists a recursive solution \((v_{t}^{*})_{t=0}^{T}\) to the Bellman recursion  
\[v_{T}^{*}(p,z) = r_{T}(p,z) \tag{13}\] \[v_{t}^{*}(p,z) = \max_{a\in A}(r_{t}(p,z,a)+\mathbb{E}(v_{t+1}^{*}(\alpha(p,a),Z_{ t+1})\,|\,Z_{t}=z)) \tag{14}\]  
for \(t=T-1,\ldots,0\), \(p\in P\), and \(z\in\mathbb{R}^{d}\). The functions \((v_{t}^{*})_{t=0}^{T}\) resulting from the backward induction are called _value functions_, they determine an optimal policy \(\pi^{*}=(\pi_{t}^{*})_{t=0}^{T-1}\) via  
\[\pi_{t}^{*}(p,z)=\operatorname{argmax}_{a\in A}\left(r_{t}(p,z,a)+\mathbb{E}( v_{t+1}^{*}(\alpha(p,a),Z_{t+1})\,|\,Z_{t}=z)\right) \tag{15}\]  
for \(p\in P\), \(z\in\mathbb{R}^{d}\), for all \(t=0,\ldots,T-1\). We shall emphasize that solutions to even simplest switching problems are sometimes surprising and non-intuitive. Frequently, observing an optimal solution helps to understand the original questions. As an illustration, we consider two classical problems (borrowed from [18]) whose solutions are non-intuitive, at a first glance. * Consider a card desk face down with \(b\in\mathbb{N}_{+}\) black and \(r\in\mathbb{N}_{+}\) red cards. On each turn, the player chooses whether to draw a card from the desk or not. If the player decides to take a card, then he gains $1 if a black card is taken, and loses $1 if a red card is drawn. Once the card is taken, it is put aside and will not be returned to the desk. Is it possible that \(b<r\) and it is still worth starting to draw? * An equal number of red and black cards \(r=b\in\mathbb{N}_{+}\) are face down on a table. I am turning the cards over one by one, and at any time you can say \"stop\" and I turn over one next card. If the card is black, you win \[v_{0}^{\pi}(p_{0},z_{0})=\mathbb{E}\left(\sum_{t=0}^{T-1}r_{t}(p_{t}^{\pi},Z_{ t},a_{t}^{\pi})+r_{T}(p_{T}^{\pi},Z_{T})\right).\]01. If you do not stop before the last card, the last card's color is used to decide whether you win or lose. What is the optimal strategy for playing this game? An analysis of the Game I shows that in some situations, it is indeed worth playing if there are more red than black cards. For instance, even for \(b=4\), \(r=6\) the value of the optimal policy is still positive, \(2/300\). In a very similar Game II, it is surprisingly never worth playing since each policy returns the same value, which is zero. The simplest and probably the most important special case of optimal stochastic switching is _optimal stopping_.