Handling nested expectations Let $(\mathbf{X^k})$ be a stochastic process defined on a suitable probability space $(\Omega, \mathcal{F}, \mathbb{P})$ where $\mathbf{X^{k+1}}=F(\mathbf{X^k}, B^k)$, $F: \mathbb{R}^n\times \{1, \dots, N\} \to \mathbb{R}^n$ such that $N \in \mathbb{N}$, $B^k \subseteq \{1, \dots, N\}$ with $S_B=|B^k|$ for $k \in \mathbb{Z}_+$, and $\mathbf{X^0}:=\mathbf{x}^0$ where $\mathbf{x}^0$ is a deterministic vector.
Let $\mathbf{Y}:=F(\mathbf{x}, B)$ be a random vector for any given deterministic vector $\mathbf{x}$ and a random set $B \subseteq \{1, \dots, N\}$ with $S_B=|B|$. Assume the following holds for suitable scalar-valued functions $h$ and $f$:
\begin{equation}
 h(\mathbf{x}) \leq f(\mathbf{x}) - \mathbf{E}_{B}[f(Y)|\mathbf{x}]\tag{1}. 
\end{equation}
Question?
Show the following holds:
\begin{equation}
\mathbf{E}_{B_0, \dots, B^{k-1}}[h(\mathbf{X}^k)] \leq \mathbf{E}_{B_0, \dots, B^{k-1}}[f(\mathbf{X}^k)]) - \mathbf{E}_{B_0, \dots, B^{k}}[f(\mathbf{X}^{k+1})]    
\end{equation}
My try
Since (1) holds for all $\mathbf{x}$, one can write the following for a random vector $\mathbf{X}^k$:
\begin{equation}
 h(\mathbf{X}^k) \leq f(\mathbf{X}^k) - \mathbf{E}_{B^k}[f(\mathbf{X}^{k+1})|\mathbf{X}^k]\tag{1}. 
\end{equation}
Then by taking the expectation with respect to all $B_0, \dots, B^{k-1}$, one can write the following:
\begin{equation}
\mathbf{E}_{B_0, \dots, B^{k-1}}[h(\mathbf{X}^k)] \leq \mathbf{E}_{B_0, \dots, B^{k-1}}[f(\mathbf{X}^k)] - \mathbf{E}_{B_0, \dots, B^{k-1}}[\mathbf{E}_{B^{k}}[f(\mathbf{X}^{k+1}) \Big\vert \mathbf{X}^{k}]  ]  
\end{equation}
Confusion
It is super obvious to my advisor that $\mathbf{E}_{B_0, \dots, B^{k-1}}[\mathbf{E}_{B^{k}}[f(\mathbf{X}^{k+1}) \Big\vert \mathbf{X}^{k}]  ] = \mathbf{E}_{B_0, \dots, B^{k}}[f(\mathbf{X}^{k+1})] $, but I do not know how to prove it.
 A: The setup has a few typos, so I'll state my interpretation.
Fix $N\in\mathbb N$ and $S_B\in\{0,\dots,N\}$. Let $[N]=\{1,\dots,N\}$ and let $\binom{[N]}{S_B}=\{B\subseteq[N]:|B|=S_B\}$ be the $S_B$-subsets of $[N]$.
Fix $n\in\mathbb N$ and let $F:\mathbb R^n\times\binom{[N]}{S_B}\rightarrow\mathbb R$.
Fix $x^0\in\mathbb R^n$ and let $(B^k)_{k\in\mathbb N\cup\{0\}}\in\binom{[N]}{S_B}^{\mathbb N\cup\{0\}}$ be random sets.
Define the random variables $X^k$ recursively by $X^0=\mathbf{x}^0$ and $X^k=F(X^{k-1},B^{k-1})$ for $k\in\mathbb N$.
Now, there are two possible cases. The first case seems more likely to me, but I'll discuss them both.

*

*The random sets $B^k$ are i.i.d. and there exist functions $h,f:\mathbb R^n\rightarrow\mathbb R$ such that $h(x)\le f(x)-\mathbb E[f(F(x,B^0))]$ for all $x\in\mathbb R^n$.

*There exist functions $h,f:\mathbb R^n\rightarrow\mathbb R$ such that $h(x)\le f(x)-\mathbb E[f(F(x,B))]$ for all $x\in\mathbb R^n$ and any choice of random set$B\in\binom{[N]}{S_B}$.

The claim is that for all $k\in\mathbb N\cup\{0\}$ we have $\mathbb E[h(X^k)]\le\mathbb E[f(X^k)]-\mathbb E[f(X^{k+1})]$.
Let's turn to the proof.
We show the result by induction.
For $k=0$ we have $\mathbb E[h(X^0)]=h(x^0)$, $\mathbb E[f(X^0)]=f(x^0)$ and $\mathbb E[f(X^1)]=\mathbb E[f(F(x^0,B^0))]$, all by definition.

*

*If the sets are i.i.d., then we have $h(x^0)\le f(x^0)-\mathbb E[f(F(x^0,B^0))]$ by assumption.

*Since the inequality holds for any random set $B$, it holds for all one-point masses, i.e. for all $b\in\binom{[N]}{S_B}$ using the random set $B\in\binom{[N]}{S_B}$ given by $\mathbb P(B=b)=1$ we have $h(x)\le f(x)-\mathbb E[f(F(x,B))]=f(x)-f(F(x,b))$ for all $x$ and $b$. This shows that $\mathbb E[f(F(x,B))]\le\mathbb E[h(x)+f(x)]=h(x)+f(x)$ for all any random set $B\in\binom{[N]}{S_B}$, and in particular that $h(x^0)\le f(x^0)-\mathbb E[f(F(x^0,B^0))]$.

So, we obtain $\mathbb E[h(X^0)]=h(x^0)\le f(x^0)-\mathbb E[f(F(x^0,B^0))]=\mathbb E[f(X^0)]-\mathbb E[f(X^1)]$ in both cases.
Now, let $k\ge 1$. Let $\mathcal B=\{(b^j)_{j<k}:\mathbb P((B^j)_{j<k}=(b^{j})_{j<k})>0\}$ be the support of $(B^j)_{j<k}$ (notice that are only finitely many outcomes for $(B^j)_{j<k}$). For $(b^j)_{j<k}\in\mathcal B$ let $x^k$ be recursively given by $x^j=F(x^{j-1},b^{j-1})$ for $j\in[k]$.
Notice that on the event $\{(B^j)_{j<k}=(b^j)_{j<k}\}$ we have $X^j=x^j$ for all $j\le k$, directly from the definition. And hence, on this event we also have $X^{k+1}=F(x^k,B^k)$. This gives
$$\mathbb E[h(X^k)|(B^j)_{j<k}=(b^j)_{j<k}]=h(x^k),
\mathbb E[f(X^k)|(B^j)_{j<k}=(b^j)_{j<k}]=f(x^k),\\
\mathbb E[f(X^{k+1})|(B^j)_{j<k}=(b^j)_{j<k}]
=\sum_{b^k}\mathbb P(B^k=b^k|(B^j)_{j<k}=(b^j)_{j<k})f(F(x^k,b^k)).$$

*

*Since $B^k$ is independent from $(B^j)_{j<k}$, we have $\mathbb P(B^k=b^k|(B^j)_{j<k}=(b^j)_{j<k})=\mathbb P(B^k=b^k)$. Since $B^k$ and $B^0$ have the same law, we have $\mathbb P(B^k=b^k)=\mathbb P(B^0=b^k)$. Combining the results gives
$$\mathbb E[h(X^k)|(B^j)_{j<k}=(b^j)_{j<k}]\le \mathbb E[f(X^k)|(B^j)_{j<k}=(b^j)_{j<k}]-\mathbb E[f(X^{k+1})|(B^j)_{j<k}=(b^j)_{j<k}]$$
since $\mathbb E[f(X^{k+1})|(B^j)_{j<k}=(b^j)_{j<k}]=\mathbb E[f(F(x^k,B^0))]$ by the above.

*Since the inequality holds for any random $B$, it in particular holds for $B^k$ given $(B^j)_{j<k}$, so by combining the results we recover
$$\mathbb E[h(X^k)|(B^j)_{j<k}=(b^j)_{j<k}]\le \mathbb E[f(X^k)|(B^j)_{j<k}=(b^j)_{j<k}]-\mathbb E[f(X^{k+1})|(B^j)_{j<k}=(b^j)_{j<k}].$$
Now, we're only left to take the expectation over the $(B^j)_{j<k}$, meaning
\begin{aligned}
\mathbb E[h(X^k)]
&=\sum_{b\in\mathcal B}\mathbb P((B^j)_{j<k}=b)\mathbb E[h(X^k)|(B^j)_{j<k}=b]\\
&\le\sum_{b\in\mathcal B}\mathbb P((B^j)_{j<k}=b)
\left(\mathbb E[f(X^k)|(B^j)_{j<k}=b]-\mathbb E[f(X^{k+1})|(B^j)_{j<k}=b]\right)\\
&=\mathbb E[f(X^k)]-\mathbb E[f(X^{k+1})].
\end{aligned}
This completes the proof.
Some remarks on the bigger picture:

*

*I deliberately chose to make use of the fact that the $B^j$ are finitely supported, meaning that I can carry all arguments through pointwise (as I call it). It is crucial to have a very, very solid understanding of working with conditional expectations in the discrete case before turning to general conditional expectations. If the answer was helpful, I would strongly recommend to carry out the proof without making use of the finite supports, only using the rules of conditional expectations.

*Notice that the proof also answers your question on the tower property. It is the last line, where we e.g. write $\mathbb E[h(X^k)]$ as the expectation over the conditional expectation, i.e.
\begin{aligned}
\mathbb E[h(X^k)]
&=\sum_{(b^j)_{j<k}\in\mathcal B}\mathbb P((B^j)_{j<k}=(b^j)_{j<k})\mathbb E[h(X^k)|(B^j)_{j<k}=(b^j)_{j<k}]\\
&=\mathbb E[\mathbb E[h(X^k)|(B^j)_{j<k}]].
\end{aligned}

*Proofs of this type are fairly frequent, by this I mean the recursive structure in the definitions and the proof itself. Examples are (variations of) martingale results, differential equation methods, recursively defined couplings or processes. This is a nice introductory example. If you want to simplify the notation and the intuition, you can consider a setup with i.i.d. Bernoulii variables $B^j$ instead of the sets.

