text:
\section{Introduction}

Network coding (NC) was proposed in \cite{Ahlswede2000} to maximize the information flow in a wired network. It was introduced in multicast wireless communications to optimize the throughput, and has gained a lot of  interest recently due to the rapid growth in multimedia applications \cite{WuXOR2004}. It was shown in \cite{KattiXOR2006} that the power efficiency in wireless transmission systems could be improved by NC. For example, in a 3-node network system, called the network-coded two-way relay channels (NC-TWRC)\cite{Hausl2006} as shown in Fig.~\ref{fig:3Node}, the messages $m_1$ and $m_2$ are XORed at the relay and broadcast to the end users. This method, compared to the conventional store-and-forward transmission, reduces the total number of transmissions from $4$ to $3$ so that the transmission power is saved by $25\%$. Since then, numerous optimization problems have been studied in NC-TWRC, e.g., training design for optimal channel estimation \cite{Gao2009} and the design principle of modulation and NC scheme\cite{Koike2009}.

\begin{figure}[h]
	\centering
		\centerline{\scalebox{1.1}{\input{figures/3Node.tex}}}
	\caption{NC-TWRC \cite{Hausl2006}. Two users exchange information ($m_1$ and $m_2$) via the center node $R$ (stands for relay).}
	\label{fig:3Node}
\end{figure}

In \cite{KattiImportance2005}, Katti et al.\ pointed out the importance of being opportunistic in practical NC scenarios. It was suggested that the assumptions in the related research work should comply with the practical wireless environments, e.g., decentralized routing and non-stationary traffic rate. This suggestion highlighted a problem in the existing literature: The majority of the studies consider synchronized traffic while ignoring the stochastic nature of the packet arrivals in the network layer. However, introducing the randomness of traffic in Fig.~\ref{fig:3Node} gives rise to a power-delay tradeoff: When there are symbol inflows in the relay but no coding opportunities or XORing pairs (e.g., one symbol arrives from one user, but no symbol arrives from the other), waiting for coding opportunities by holding symbols saves transmission power but increases symbol delay. This dilemma was studied and solved by NC-TWRC with buffering in \cite{ChenONC2007} and \cite{HsuONC2011}. It was shown that the optimal transmission policy by a Markovian process formulation minimized the transmission power and symbol delay simultaneously and in the long run. In \cite{Ding2012}, the NC-TWRC in \cite{ChenONC2007,HsuONC2011} was extended to include the dynamics of wireless channels (Fig.~\ref{fig:2U1R_M_W}). In this system, a transmission policy that solves power-delay tradeoff may not be the best decision rule because it does not consider the possible loss in throughput due to the downlink transmission errors. For this reason, the scheduler is required to make optimal decision that simultaneously minimizes the transmission power, symbol delay, downlink BER in the long run by considering current queue and channel states and their expectations in the future. In \cite{Ding2012}, this problem was formulated by a discounted infinite horizon Markov decision process (MDP) with channels modeled by finite-state Markov chains (FSMCs)\cite{Sadeghi2008}. The optimal transmission policy searched by dynamic programming (DP) was shown to be superior to \cite{ChenONC2007} and \cite{HsuONC2011} in terms of enhancing the QoS (quality of service, evaluated by symbol delay and overflow in the data link layer and power consumption and error rate in the physical layer) in a practical wireless environment, e.g., Rayleigh fading channels.

\begin{figure}[h]
	\centering
		\centerline{\scalebox{1.1}{\input{figures/SYSTEM.tex}}}
	\caption{NC-TWRC with random symbol arrivals and fading channels \cite{Ding2012}. The stochastic inflows are buffered by two finite length first-in-first-out (FIFO) queues. The outflows are controlled by a scheduler. }
	\label{fig:2U1R_M_W}
\end{figure}

However, the DP algorithm in \cite{Ding2012} is burdened with high complexity. The scheduler requires information of both queue states/occupancies and channel states to assist the decision making, i.e., the system state is a $4$-tuple (two channels and two queues) and the decision/action is a $2$-tuple (each associated with the departure control of one queue). In such a high dimensional MDP, \emph{the curse of dimensionality}\footnote{The complexity of the algorithm grows exponentially with the cardinality of the system variables \cite{SuttonRL1998}.} becomes more evident. The problem could be intractable if the cardinality of any tuple in the state variable is large. To relieve the curse, one solution is to qualitatively understand the model and prove the existence of a structured optimal policy \cite{Smith2002}. Then a modified DP algorithm, or an alternative algorithm with lower complexity, can be proposed. For example, if the optimal policy is proved to be nondecreasing in the state variable, we can run a monotonic policy iteration \cite{Djonin2007}, which reduces the computation load by shrinking the feasible action space with the increasing state index in each iteration of DP; if the optimal policy is of threshold type, the problem can be solved by a simultaneous perturbation stochastic approximation (SPSA) algorithm \cite{Huang2010}. But, structured optimal policy does not exist in general. Most often, optimal policy exists, but it varies with the state variable irregularly. In order to prove the existence of certain feature (e.g., monotonicity) in the optimal policy, we need to extensively analyze the MDP model and the recursive functions in DP algorithm. The basic approach in the existing literature is to show by induction that the monotonicity/submodularity is preserved in each iterative optimization process (maximization/minimization) in DP, e.g., \cite{Huang2010,Djonin2007}. We adopt the same method in this paper, but consider these properties in high dimensional cases. For example, a 3-dimensional submodularity (instead of 2-dimensional as usual) is shown to contribute to a monotonic optimal solution in both queue and channel states. Moreover, we use $L^{\natural}$-convexity and multimodularity, two concepts that were originally defined in discrete convex analysis \cite{Topkis2001,Murota2005} and recently applied in operational research \cite{Zhuang2012,Zipkin2008,Pang2012}, to describe the joint submodularity and integral convexity in a high dimensional space.

The aim of our work is to establish the sufficient conditions for the existence of a monotonic optimal transmission policy in the NC-TWRC system in Fig.~\ref{fig:2U1R_M_W}. Unlike other related research work where certain features were assumed \textit{a priori} (e.g., strict submodularity of DP functions \cite{Hoang2008} or uniformly distributed traffic flows \cite{Huang2010}), we prove the properties of DP by observing the variation of parameters in the immediate cost function of MDP (e.g., unit costs associated with symbol delay and transmission power, quantized error rate associated with the channel state, etc.) while having our assumptions consistent with the actual applications (e.g., arbitrary traffic rates, flat and slow Rayleigh fading channels). The main results in this paper are:
\begin{itemize}
    \item We prove that each tuple in the optimal policy is nondecreasing in the queue state that is controlled by that tuple if the chosen values of unit costs give rise to an $L^{\natural}$-convex or multimodular DP. Moreover, we show that the same results found in \cite{Huang2010} and \cite{Djonin2007} can also be explained by $L^{\natural}$-convexity or multimodularity by a unimodular coordinate transform \cite{Yu2013}.
    \item By thinking of each iteration in DP as a one-stage pure coordination supermodular game, we show that equiprobable traffic rates and certain conditions on unit costs guarantee that each tuple in the optimal policy is monotonic in not only the queue state that is controlled by that tuple but also the queue state that is associated with the information flow of the opposite direction, i.e. the one that is not under the control of that tuple.
    \item By observing the submodularity of DP, we show the sufficient conditions for an optimal policy to be nondecreasing in both queue and channel states in terms of unit costs, channel statistics, FSMC models and modulation scheme.
\end{itemize}

The rest of this paper is organized as follows. In Section~\ref{sec:sys}, we state the optimization problem in NC-TWRC with random symbol arrivals and FSMC modeled channels and clarify the assumptions of this system. In Section~\ref{sec:MDP}, we describe the MDP formulation, state the objective and present the DP algorithm. In Section~\ref{sec:Struct}, we investigate the structure in the optimal transmission policy found by DP algorithm in queue and channel states, where numerical examples are presented.

\section{System}
\label{sec:sys}

\subsection{NC-TWRC with random symbol arrivals and wireless fading channels}

Consider the NC-TWRC shown in Fig.~\ref{fig:2U1R_M_W}. User 1 and 2 randomly send symbols to each other via the relay. The relay is equipped with two finite-length FIFO queues, queue $1$ and $2$, to buffer the incoming symbols from user $1$ and $2$, respectively. The outflows of queues are controlled by a scheduler. The scheduler keeps making decisions as to whether or not to transmit symbols from queues. If the decision results in a pair of symbols in opposite directions transmitted at the same time, they will be XORed (coded) and broadcast. Otherwise, the symbol will be simply forwarded to the end user. The optimization problem is to find an optimal transmission control policy that minimizes symbol delay, queue overflow, transmission power (saved by utilizing the coding opportunities) and downlink transmission errors simultaneously and their expectations in the future.

Obviously, the optimization concerns are contradictory to each other: (1) Because of the random symbol inflows, there would not always be a pair of symbols for XORing. In this situation, waiting for coding opportunity by holding symbols results in a high symbol delay on average, while transmitting a symbol without coding results in one more symbol to be transmitted in the future, i.e., more transmission power on average; (2) Even if there is a coding opportunity, broadcasting a coded symbol when any of the channels is having low SNR will incur a high symbol error rate. Therefore, the scheduler must seek an optimal decision rule that solves this \textit{power-delay-error tradeoff}.

\subsection{Assumptions}

We consider a discrete-time decision making process, where the time is divided into small intervals, called \textit{decision epochs} and denoted by $t\in\{0,1,\dotsc,T\}$. Let $i\in\{1,2\}$ and assume the following:
\begin{enumerate}[{A}1]

\item (\emph{i.i.d.} \ incoming traffic) Denote random variable $f_i^{(t)}\in{\mathcal{F}_i}$ as the number of incoming symbols to queue $i$ at decision epoch $t$. Let the maximum number of symbols arrived per decision epoch be no greater than $1$, i.e., $\mathcal{F}_i=\{0, 1\}$. Assume that $\{f_1^{(t)}\}$ and $\{f_2^{(t)}\}$ are two independent \emph{i.i.d.}\ random processes with $Pr(f_i^{(t)}=1)=p_i$ and $Pr(f_i^{(t)}=0)=1-p_i$ for all $t$. Since the traffic flow rate is maximum one symbol per decision epoch, the length of decision epoch is equal to the symbol duration.

\item (finite-length queues) Queue $i$ can store maximum $L_i$ symbols. At each $t$, the scheduler makes a decision and incurs an immediate cost before the event $\mathbf{f}^{(t)}=(f_1^{(t)},f_2^{(t)})$. Denote $b_i^{(t)}\in{\B_i}$ as the occupancy of queue $i$ at the beginning of decision epoch $t$, then $\B_i=\{0,1,\dotsc,L_i+\max{\{f_i^{(t-1)}\}}\}=\{0,1,\dotsc,L_i+1\}$. If the relay's decision results in queue occupation $L_i+1$, the newly arrived symbol will be dropped. We call it symbol lost due to the \textit{queue overflow}.

\item (Markovian channel modeling) Let the full variation range of $\gamma_i^{(t)}$, the instantaneous SNR of channel $i$, be partitioned into $K_i$ non-overlapping regions $\{[\Gamma_1,\Gamma_2),[\Gamma_2,\Gamma_3),\dotsc,[\Gamma_{K_i},\infty)\}$, called channel states. Denote $\G_i=\{1,2,\dotsc,K_i\}$ as the state set of channel $i$ and $g_i^{(t)}$ as the state of channel $i$ at decision epoch $t$. We say that $g_i^{(t)}=k_i$ if $\gamma_i^{(t)}\in{[\Gamma_{k_i},\Gamma_{k_i+1})}$. Each channel is modeled by a finite-state Markov chain (FSMC) \cite{Sadeghi2008}, where the state evolution of channel $i$ is governed by the transition probability $P_{g_i^{(t)}g_i^{(t+1)}}=Pr(g_i^{(t+1)}|g_i^{(t)})$.

\item (downlink channel state information) Let $\{g_1^{(t)}\}$ and $\{g_2^{(t)}\}$ be two independent and \textit{i.i.d.}\ random processes. The relay has the channel state information (channel state $g_i^{(t)}$ and transition probability $P_{g_i^{(t)}g_i^{(t+1)}}$) of both channels before the decision making at $t$.

\end{enumerate}

\section{Markov Decision Process Formulation}
\label{sec:MDP}

Based on A1, A3 and A4, we know that the statistics of the incoming traffic flow and channel dynamics associated with user $1$ or $2$ are time-invariant. It follows that the transmission control problem in Fig.~\ref{fig:2U1R_M_W} can be formulated as a stationary Markov decision process (MDP). In the following context, we drop the decision epoch notation $t$ in A1-A4 and use the notation $y$ and $y'$ for the system variable $y$ at the current and next decision epochs, respectively.

\subsection{System State}

Denote the system state $\mathbf{x}=(\mathbf{b}, \mathbf{g})\in{\mathcal{X}}$, where $\mathbf{b}=(b_1,b_2)\in{\B_1\times{\B_2}}$ and $\mathbf{g}=(g_1,g_2)\in{\G_1\times{\G_2}}$, i.e., $\mathcal{X}=\B_1\times{\B_2}\times{\G_1}\times{\G_2}$. $\times$ denotes the Cartesian product. We also use the 4-tuple notation $\mathbf{x}=(b_1,b_2,g_1,g_2)$ in the following context.

\subsection{Action}

Denote action $\mathbf{a}=(a_1,a_2)\in{\mathcal{A}}$, where $a_i\in{\mathcal{A}_i}=\{0,1\}$ denotes the number of symbols departed from queue $i$ and $\mathcal{A}=\mathcal{A}_1\times{\mathcal{A}_2}=\{0,1\}^2$. The terminology of actions are shown in Table~\ref{tab:ActionSet}.

\begin{table}[tbp]
	\renewcommand{\arraystretch}{1.3}
	\caption{Action Set}
	\label{tab:ActionSet}
	\centering

	\begin{tabular}{c c}
	\hline\hline
	$\mathbf{a}$& \bfseries action itemize \\ %
	\hline
	$(0,0)$ & no transmission \\
	$(1,0)$ & forward one symbol in queue 1  \\
	$(0,1)$ & forward one symbol in queue 2 \\
	$(1,1)$ & XOR two symbols one in each queue, then broadcast.\\[0.3ex]
	\hline
	\end{tabular}
\end{table}

\subsection{State Transition Probabilities}

The transition probability $P_{\x\x^\prime}^\act=Pr(\mathbf{x}|\mathbf{x}',\mathbf{a})$ denotes the probability of being in state $\mathbf{x}'$ at next decision epoch if action $\mathbf{a}$ is taken in state $\mathbf{x}$ at current decision epoch. Due to the assumptions of independent random processes in A1 and A4, the state transition probability is given by
\begin{equation}
    P_{\x\x^\prime}^\act=P_{\bv\bv'}^{\act}P_{\gv\gv'}=\prod_{i=1}^{2}P_{b_ib_i^\prime}^{a_i}P_{g_ig_i^\prime},
\end{equation}
where $P_{g_ig_i^\prime}$ is determined by channel statistics and FSMC modeling method in A3 and $P_{b_ib_i^\prime}^{a_i}$ is the queue state transition probability derived as follows.

At current decision epoch, the occupancy of queue $i$ after decision $a_i$ is $\min\{[b_i-a_i]^{+},L_i\}$, where $[y]^{+}=\max\{y,0\}$. Then, the occupancy at the beginning of the next decision epoch is given by
\begin{equation}
    b'_i=\min\{[b_i-a_i]^{+},L_i\}+f_i.
\end{equation}
Therefore, the state transition probability of queue $i$ is
\begin{align}
P_{b_ib_i^\prime}^{a_i}&=Pr\left(f_i=b_i^{\prime}-\min\{[b_i-a_i]^{+},L_i\}\right)                        \nonumber \\
     &=Pr\left(f_i=b_i^{\prime}-[b_i-a_i]^{+}+\mathcal{I}_{\{[b_i-a_i]^{+}>L_i\}}\right)       \nonumber \\
     &=\begin{cases}
		  Pr(f_i=b_i^{\prime}-[b_i-a_i]^{+}) & [b_i-a_i]^{+}\leq{L_i}\\
		  Pr(f_i=b_i^{\prime}-L_i) & [b_i-a_i]^{+}>L_i
	   \end{cases},
\end{align}
where $\mathcal{I}_{\{\cdot\}}$ is the indicator function that returns $1$ if the expression in $\{\cdot\}$ is true and $0$ otherwise.

\subsection{Immediate Cost}

$C:\mathcal{X}\times\mathcal{A}\rightarrow{\mathbb{R}_+}$ is the cost incurred immediately after action $\mathbf{a}$ is taken in state $\mathbf{x}$ at current decision epoch. It reflects three optimization concerns: the symbol delay and queue overflow, the transmission power and the downlink transmission error rate.

\subsubsection*{Holding and overflow cost}

We define $h_i$, the holding and queue overflow cost associated with queue $i$, as
  \begin{align}
        h_i(y_i)&=\lambda\min\{[y_i]^+,L_i\}+\xi_o\mathcal{I}_{\{[y_i]^+=L_i+1\}}  \nonumber \\
                        &=\lambda[y_i]^{+}+(\xi_o-\lambda)\mathcal{I}_{\{[y_i]^{+}=L_i+1\}}.
  \end{align}
  $\lambda>0$ is the unit holding cost and $\xi_o>\lambda$ is the unit queue overflow cost, which makes $h_i(y_i)$ a nondecreasing convex function. In the case when $y_i=b_i-a_i$, $\min\{[y_i]^+,L_i\}$ and $\mathcal{I}_{\{[y_i]^+=L_i+1\}}$ count the number of symbols held in queue $i$ and the number of symbols lost due the overflow of queue $i$, respectively. We say that the term $\lambda\min\{[y_i]^+,L_i\}$ accounts for the symbol delay because by Little's Law the average symbol delay is proportional to the average number of symbols held in the queue in the long run for a given symbol arrival rate \cite{Yang2012}. We sum up $h_i$ for $i\in\{1,2\}$ and obtain the total holding and overflow cost as
  \begin{equation} \label{eq:HoldCost}
        C_{h}(\mathbf{b},\mathbf{a})=\sum_{i=1}^{2}h_i(b_i-a_i).
  \end{equation}

\subsubsection*{Transmission cost}

Since forwarding and broadcasting one symbol, either coded or non-coded, consume the same amount of power, we have the immediate transmission cost as
  \begin{equation}\label{eq:TransCost}
        t_r(\mathbf{a})=\tau\mathcal{I}_{\{a_1=1 \text{ or }a_2=1\}}=
            \begin{cases}
		      0 & \mathbf{a}=(0,0)\\
		      \tau & \text{otherwise}
	       \end{cases},
  \end{equation}
where $\tau>\lambda$ is the unit transmission cost and $\mathcal{I}_{\{a_1=1 \text{ or }a_2=1\}}$ counts the number of transmissions resulting from action $\mathbf{a}$.

Note that \eqref{eq:HoldCost} and \eqref{eq:TransCost} form a power-delay tradeoff. A policy that always transmits whenever there is an incoming symbol without considering coding opportunities in the long run is penalized by \eqref{eq:TransCost}, and a policy that always holds symbol to wait for coding opportunities without considering the average symbol delay is penalized by \eqref{eq:HoldCost}.

\subsubsection*{Symbol error cost}

Let $P_e(g_i)$ denote the symbol error probability when channel $i$ is in state $g_i$. The form of the function $P_e$ is determined by the modulation scheme (e.g., $P_e(g_i)=\frac{1}{2}\erfc(\sqrt{\Gamma_{g_i}})$ for BPSK modulation). And, $P_e(g_i)\leq{0.5}$ for all $g_i$ because $\Gamma_1\geq{0}$ in A3. Since symbol errors happen only when we decide to transmit, we define the immediate symbol error cost due to the action $a_i$ as
  \begin{equation} \label{eq:ErrCost}
        \err(g_{-i},a_i)=\eta a_iP_e(g_{-i}),
  \end{equation}
where $\eta$ is the unit symbol error cost and $-i\in\{1,2\}\setminus\{i\}$, i.e., $-i=2$ if $i=1$, and $-i=1$ if $i=2$. Note, the reason we have $\err(g_{-i},a_i)$ is because the symbol departing queue $i$ is transmitted through channel $-i$, e.g., the relay sends one symbol in queue $1$ through fading channel $2$ when $a_1=1$.

Note, the aforementioned power-delay tradeoff formed by \eqref{eq:HoldCost} and \eqref{eq:TransCost} just poses the problem: whether or not to transmit if an instantaneous symbol inflow is not able to form an XORing pair. However, if the scheduler considers downlink transmission error rate in addition, a policy that always broadcasts XORed symbols whenever there's a coding opportunity without considering downlink channel states is penalized by \eqref{eq:ErrCost}. Therefore, \eqref{eq:HoldCost}, \eqref{eq:TransCost} and \eqref{eq:ErrCost} form a power-delay-error tradeoff.

In summary, we define the immediate cost as
\begin{equation}
        C(\mathbf{x},\mathbf{a})=C(\mathbf{b},\mathbf{g},\mathbf{a})=C_{h}(\mathbf{b},\mathbf{a})+C_{t}(\mathbf{g},\mathbf{a}),
\end{equation}
where
\begin{align}
    C_{t}(\mathbf{g},\mathbf{a}) &= \sum_{i=1}^{2}\err(g_{-i},a_i)+t_r(\mathbf{a}) \nonumber\\
    &= \eta\sum_{i=1}^{2}a_iP_e(g_{-i})+\tau\mathcal{I}_{\{a_1=1\ or\ a_2=1\}}.
\end{align}

Here, $C(\mathbf{x},\mathbf{a})$ is in fact a linear combination of loss functions (each quantifies an optimization concern). The unit cost $\lambda$, $\xi_o$, $\tau$ and $\eta$ can be considered as the weight factors that are either given or adjustable depending on the real applications. In Section~\ref{sec:Struct}, we will derive the sufficient conditions of the existence of a structured optimal policy mainly in terms of the chosen values of these unit costs.

\subsection{Objective and Dynamic Programming}

Let $\mathbf{x}^{(t)}$ and $\mathbf{a}^{(t)}$ denote the state and action at decision epoch $t$, respectively, and consider an infinite-horizon MDP modeling where the discrete decision making process is assumed to be infinitely long. We can describe the long-run objective as
\begin{align} \label{eq:obj}
        \min\mathbb{E}\left[\sum_{t=0}^{\infty} \beta^t C(\mathbf{x}^{(t)},\mathbf{a}^{(t)})|\mathbf{x}^{(0)}\right], \forall{\mathbf{x}^{(0)}\in{\mathcal{X}}},
\end{align}
where $\beta\in[0,1)$ is the discounted factor that ensures the convergence of the series. It is proved in \cite{PutermanMDP1994}, that if the state space $\mathcal{X}$ is countable, the action set $\mathcal{A}$ is finite and the MDP is stationary, there exists an optimal deterministic stationary policy $\theta^*:\mathcal{X}\rightarrow{\mathcal{A}}$, and $\theta^*$ can be searched by dynamic programming (DP)
\begin{align}
    &Q^{(n)}(\mathbf{x},\mathbf{a})=C(\mathbf{x},\mathbf{a})+\beta\smashoperator{\sum_{\mathbf{x}'\in{\mathcal{X}}}} P_{\x\x^\prime}^\act  V^{(n-1)}(\mathbf{x}'),      \\
    &V^{(n)}(\mathbf{x})=\min_{\mathbf{a}\in{\mathcal{A}}}Q^{(n)}(\mathbf{x},\mathbf{a}),
\end{align}
where $n$ denotes the iteration index, $V^{(0)}=0$ for all $\mathbf{x}$ and the optimal policy $\theta^*(\mathbf{x})=\arg\min_{\mathbf{a}\in{\mathcal{A}}}Q^{(N)}(\mathbf{x},\mathbf{a})$ if DP converges at $N$th iteration. Usually a very small convergence threshold is applied, i.e., $N<\infty$.

\section{Structured Optimal Policies}
\label{sec:Struct}

A conventional transmission control MDP model, say \cite{Hoang2008} for adaptive modulation purpose, usually has $2$-tuple state and $1$-tuple action variables. However, the MDP model defined in Section~\ref{sec:MDP} has a higher dimension: $4$-tuple state and $2$-tuple action. This could make the DP algorithm cumbersome. The major problem with DP is the \textit{curse of dimensionality}, the computation load grows exponentially with the number and dimensions of system parameters. The consequence is that the optimization problem may become intractable. For example, an increment in the cardinality of any tuple in the state variable $\mathbf{x}=(b_1,b_2,g_1,g_2)$ may severely overload the CPU in DP iterations or, even worse, drive the processer out of memory during MDP modeling. To cope with this problem, researchers are always interested in certain structures, e.g., monotonicity, in the optimal policy because a modified optimization algorithm with lower complexity, e.g., structured policy iteration \cite{Djonin2007} or simultaneous perturbation stochastic approximation (SPSA) \cite{Huang2010}, can be proposed if so. In this section, we investigate the submodularity, $L^{\natural}$-convexity and multimodularity of functions $Q^{(n)}(\mathbf{x},\mathbf{a})$ and $V^{(n)}(\mathbf{x})$ in DP to establish the sufficient conditions for the existence of a monotonic optimal policy. Before that, we clarify some concepts\footnote{The definitions and lemmas related to submodularity are based on functions defined on a lattice \cite{Topkis2001}. We omitted the notation of ``lattice'' because it is obvious that queue/channel state space in our model is a complete lattice, which can be verified using the definition in \cite{Topkis1978}.} as follows.

\begin{definition}[Monotonic policy] \label{def:monotone}
Let $\theta\colon\mathbb{Z}^n\rightarrow{\mathbb{Z}^m}$, $\theta(\mathbf{x})$ is monotonic nondecreasing if $\theta(\mathbf{x}^+)\succeq{\theta(\mathbf{x}^-})$, for all $\mathbf{x}^+,\mathbf{x}^-\in{\mathbb{Z}^n}$ such that $\mathbf{x}^+\succeq{\mathbf{x}^-}$, where $\succeq$ denotes componentwise greater than or equal to.
\end{definition}

In the case when $|\mathcal{X}|\gg{|\mathcal{A}|}$, a nondecreasing optimal policy is in the form of
    \begin{equation}
        \theta^{*}(\mathbf{x})= \begin{cases}
                            \mathbf{a}_{|\mathcal{A}|}  &  \phi_{\mathbf{a}_{|\mathcal{A}|}}^*\preceq{\mathbf{x}}   \\
                            \qquad \vdots   \\
                            \mathbf{a}_2       &  \phi_{\mathbf{a}_1}^*\preceq{\mathbf{x}}\prec{\phi_{\mathbf{a}_2}^*}  \\
                            \mathbf{a}_1       &  \mathbf{x}\prec{\phi_{\mathbf{a}_1}^*}
                         \end{cases}.
    \end{equation}
$\theta^{*}$ is a switching curve or plane that is characterized by optimal threshold vector
\begin{equation}
    \Thv=(\phi_{\mathbf{a}_1}^*,\phi_{\mathbf{a}_2}^*,\cdots,\phi_{\mathbf{a}_{|\mathcal{A}|}}^*).
\end{equation}
In this case, we can formulate a multivariate optimization problem in the form of
\begin{equation}
    \min_{\Thv}J(\Thv)
\end{equation}
with $J$ being the objective in \eqref{eq:obj}. This problem can be solved by an SPSA algorithm, e.g., \cite{Huang2010}.

\begin{definition}[Submodularity] \label{def:submodularity}
Let $\mathbf{e}_i\in{\mathbb{Z}^n}$ be an $n$-tuple with all zero entries except the $i$th entry being one. $f\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ is submodular if $f(\mathbf{x}+\mathbf{e}_i)+f(\mathbf{x}+\mathbf{e}_j)\geq{f(\mathbf{x})+f(\mathbf{x}+\mathbf{e}_i+\mathbf{e}_j)}$ for all $\mathbf{x}\in{\mathbb{Z}^n}$ and $1 \leq i,j \leq n$ such that $i\neq{j}$. $f$ is strictly submodular if the inequality is strict.\footnote{This definition is based on the submodularity defined on lattice in \cite{Murota2005} and Proposition 2.1 in \cite{Hajek1985}}
\end{definition}

The insight of the submodularity can be explained by the following example. In DP, a submodular function $Q^{(n)}(\mathbf{x},\mathbf{a})$ has $Q^{(n)}(\mathbf{x},\mathbf{a}^-)-Q^{(n)}(\mathbf{x},\mathbf{a}^+)$ nondecreasing in $\mathbf{x}$ for all $\mathbf{a}^+\succeq{\mathbf{a}^-}$\footnote{According to Definition~\ref{def:submodularity}, $Q(\mathbf{x},\mathbf{a})$ is submodular if $Q(\mathbf{x}^+,\mathbf{a}^-)-Q(\mathbf{x}^+,\mathbf{a}^+)\geq{Q(\mathbf{x}^-,\mathbf{a}^-)-Q(\mathbf{x}^-,\mathbf{a}^+)}$ for all $\mathbf{a}^+\succeq{\mathbf{a}^-}$ and $\mathbf{x}^+\succeq{\mathbf{x}^-}$.}, i.e., the preference of choosing action $\mathbf{a}^+$ over $\mathbf{a}^-$ is always nondecreasing in $\mathbf{x}$. Therefore, an increase in the state variable $\mathbf{x}$ implies an increase in the decision rule $\theta^{(n)}(\mathbf{x})=\min_{\mathbf{a}}Q^{(n)}(\mathbf{x},\mathbf{a})$. It follows that the optimal policy $\theta^*(\mathbf{x})=\min_{\mathbf{a}}Q^{(N)}(\mathbf{x},\mathbf{a})$ must be monotonic in $\mathbf{x}$ if we can prove the submodularity of $Q^{(n)}$ for all $n$. This property is summarized in a general form in the following lemma.

\begin{lemma}  \label{lemma:SubmodularPreserve}
Submodularity has the following properties:
\begin{enumerate}[(a)]
  \item If $g\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ is submodular in $(\mathbf{x},\mathbf{y})\in{\mathbb{Z}^n}$, then $f(\mathbf{x})=\min_{\mathbf{y}}g(\mathbf{x},\mathbf{y})$ is submodular in $\mathbf{x}$, and the minimizer $\mathbf{y}^*(\mathbf{x})=\arg\min_{\mathbf{y}}g(\mathbf{x},\mathbf{y})$ is nondecreasing in $\mathbf{x}$. (Theorem 4.3 and 6.1 in \cite{Topkis1978})
  \item If $f_i\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ is submodular in $\mathbf{x}\in{\mathbb{Z}^n}$ and $\alpha_i\geq{0}$ for all $i$, then $\sum_{i=1}^{m} \alpha_i f_i(\mathbf{x})$ is submodular in $\mathbf{x}$. (Proof in Appendix~\ref{app:SubmodularPreserve}) \hfill\IEEEQED
\end{enumerate}
\end{lemma}

\begin{definition}[$L^{\natural}$-convexity \cite{Murota2005}] \label{def:Lconvex}
$f\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ is $L^{\natural}$-convex if $\psi(\mathbf{x},\zeta)=f(\mathbf{x}-\zeta\mathbf{1})$ is submodular in $(\mathbf{x},\zeta)$, where $\mathbf{1}=(1,1,\dotsc,1)\in{\mathbb{Z}^n}$ and $\zeta\in{\mathbb{Z}}$.
\end{definition}

\begin{definition}[multimodularity \cite{Murota2005}] \label{def:multimodular}
$f\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ is multimodular if $\psi(\mathbf{x},\zeta)=f(x_1-\zeta,x_2-x_1,\dotsc,x_n-x_{n-1})$ is submodular in $(\mathbf{x},\zeta)$, where $\zeta\in{\mathbb{Z}}$.
\end{definition}

$L^{\natural}$-convexity and multimodularity are two concepts defined in discrete convex analysis \cite{Murota2003}. $L^{\natural}$-convexity and multimodularity both imply integral convexity. The difference is that $L^{\natural}$-convexity is submodular while multimodularity is supermoduar\footnote{$f\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_-}$ is (strictly) supermodular if $-f$ is (strictly) submodular.} \cite{Yu2013}. The two concepts are related by a unimodular coordinate transform.

\begin{lemma}[unimodular coordinate transform \cite{Yu2013}] \label{lemma:UniTrans}
Let matrix $M_{n,i}=\left[ \begin{array}{ccc}
-U_i & 0  \\
0 & L_{n-i}  \end{array} \right]$, where $U_i$ and $L_{i}$ are the $i\times{i}$ upper and lower triangular matrix with all nonzero entries being one, respectively, then
\begin{enumerate}[(a)]
  \item a function $f\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ is multimodular if and only if it can be represented by $f(\mathbf{x})=g(\pm M_{n,i}\mathbf{x})$ for some $L^{\natural}$-convex function $g$.
  \item a function $g\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ is $L^{\natural}$-convex if and only if it can be represented by $g(\mathbf{x})=f(\pm M_{n,i}^{-1}\mathbf{x})$ for some multimodular function $f$. \hfill\IEEEQED
\end{enumerate}
\end{lemma}

$L^{\natural}$-convexity and multimodularity are properties commonly seen in MDP modeled flow control problems in queueing networks \cite{Altman2000} and inventory systems \cite{Zipkin2008}. Due to the implication of the submodularity/supermodularity, they both contribute to a monotonic structure in the optimal policy. In section~\ref{sec:StructB}, we will use them to show a nondecreasing optimal transmission policy in queue states. As a preliminary step, we clarify some properties of $L^{\natural}$-convexity and multimodularity in the following lemma.

\begin{lemma}  \label{lemma:LconvexPreserve}
$L^{\natural}$-convexity and multimodularity have the following properties:
\begin{enumerate}[(a)]
  \item If $g\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ is $L^{\natural}$-convex/multimodular in $(\mathbf{x},\mathbf{y})\in\mathbb{Z}^n$, then $f(\mathbf{x})=\min_{\mathbf{y}}g(\mathbf{x},\mathbf{y})$ is $L^{\natural}$-convex/multimodular in $\mathbf{x}$, and the minimizer $\mathbf{y}^*(\mathbf{x})=\arg\min_{\mathbf{y}}g(\mathbf{x},\mathbf{y})$ is nondecreasing/nonincreasing in $\mathbf{x}$. (Proof in Appendix~\ref{app:SubmodularPreserve})
  \item If $f_i\colon\mathbb{Z}^n\rightarrow\mathbb{R}_+$ is $L^{\natural}$-convex/multimodular and $\alpha_i\geq{0}$ for all $i$, then $\sum_{i=1}^{m} \alpha_i f_i(\mathbf{x})$ is $L^{\natural}$-convex/multimodular in $\mathbf{x}$. (Proof in Appendix~\ref{app:SubmodularPreserve})
  \item If $h\colon\mathbb{Z}\rightarrow{\mathbb{R}_+}$ is convex\footnote{The one dimensional discrete convex function $h:\mathbb{Z}\rightarrow{\mathbb{R}}$ satisfies $h(x+1)+h(x-1)-2h(x)\geq{0}$ for all $x\in{\mathbb{Z}}$. Moreover, by Definition~\ref{def:Lconvex} and \ref{def:multimodular}, $h$ is both $L^{\natural}$-convex and multimodular.}, then $f(\mathbf{x})=h(x_1-x_2)$ is $L^{\natural}$-convex in $\mathbf{x}=(x_1,x_2)$ and $g(\mathbf{x})=h(x_1+x_2)$ is multimodular in $\mathbf{x}=(x_1,x_2)$. (Proof in Appendix~\ref{app:SubmodularPreserve})
  \item Let $d$ be a random variable. If $g(\mathbf{x},d)$ is $L^{\natural}$-convex/multimodular in $\mathbf{x}\in{\mathbb{Z}^n}$ for all $d$, then $\mathbb{E}_{d}[g(\mathbf{x},d)]$ is $L^{\natural}$-convex/multimodular in $\mathbf{x}$. \cite{Zipkin2008,Yu2013}
  \item If $f\colon\mathbb{Z}^n\rightarrow\mathbb{R}_+$ is $L^{\natural}$-convex, then $\psi(\mathbf{x},\zeta)=f(\mathbf{x}-\zeta\mathbf{1})$ is $L^{\natural}$-convex in $(\mathbf{x},\zeta)$. (Lemma 1 in \cite{Zipkin2008})  \hfill\IEEEQED
\end{enumerate}
\end{lemma}

\begin{definition}[First order stochastic dominance \cite{Smith2002}] \label{def:1stStoDom}
Let $\tilde{\rho}(x)$ be a random selection on space $\mathcal{X}$ according to a probability measure $\mu(x)$ where $x$ conditions the random selection, then $\tilde{\rho}(x)$ is first order stochastically nondecreasing in $x$ if $\mathbb{E}[u(\tilde{\rho}(x^+))] \geq \mathbb{E}[u(\tilde{\rho}(x^-))]$ for all nondecreasing functions $u$ and $x^+ \geq x^-$.
\end{definition}

Stochastic dominance, as defined in decision theory, describes the situation that the expected aftermath (quantified by a utility or cost function) of one decision is superior to that of another. In Section~\ref{sec:StructG}, we will show that the stochastic dominance of the channel state transition probabilities preserves submodularity across the iterations in DP and contributes to a nondecreasing optimal transmission policy in channel states.

\subsection{Structured Properties of Dynamic Programming}

To propose the prototypical procedure of proving the existence of a monotonic optimal policy, we first define a $\Pro$ property as follows:
\begin{definition}[$\Pro$ property] \label{def:PstarProperty}
$f\colon\mathbb{Z}^n\rightarrow{\mathbb{R}_+}$ has $\Pro$ property in $(\mathbf{x},\mathbf{y})\in{\mathbb{Z}^n}$ if $f^*(\mathbf{x})=\min_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$ has $\Pro$ property in $\mathbf{x}$ and $\mathbf{y}^*(\mathbf{x})=\arg\min_{\mathbf{x}}f(\mathbf{x},\mathbf{y})$ is monotonic (nondecreasing/nonincreasing) in $\mathbf{x}$.
\end{definition}

It can be seen, by Lemma~\ref{lemma:SubmodularPreserve}(a) and \ref{lemma:LconvexPreserve}(a), that submodularity, $L^{\natural}$-convexity and multimodularity satisfy the conditions in Definition~\ref{def:PstarProperty}, which we summarize as follows.
\begin{theorem} \label{theo:PstarProperty}
Submodularity, $L^{\natural}$-convexity and multimodularity have $\Pro$ property.  \hfill\IEEEQED
\end{theorem}

We therefore propose an approach, similar to Proposition 5 in \cite{Smith2002}, as follows:
\begin{proposition} \label{prop:PropertyDP}
Let DP converge at $N$th iteration. The optimal value function $V^{*}(\mathbf{x})=V^{(N)}(\mathbf{x})$ has $\Pro$ property, and the optimal policy $\theta^*$ is monotonic in $\mathbf{x}$, if:
\begin{itemize}
  \item[(a)] $C(\mathbf{x},\mathbf{a})$ has $\Pro$ property,
  \item[(b)] $Q^{(n)}(\mathbf{x},\mathbf{a})=C(\mathbf{x},\mathbf{a})+\beta\sum_{\mathbf{x}'\in{\mathcal{X}}}P_{\x\x^\prime}^\act V^{(n-1)}(\mathbf{x}')$ has $\Pro$ property for all $\Pro$ property functions $V^{(n-1)}$ and $n$.
\end{itemize}
\end{proposition}
\begin{IEEEproof}
Since DP starts from $V^{(0)}(\mathbf{x})=0$ for all $\mathbf{x}\in{\mathcal{X}}$, $Q^{(1)}=C(\mathbf{x},\mathbf{a})$ has $\Pro$ property. So $V^{(1)}(\mathbf{x})=\min_{\mathbf{a}\in{\mathcal{A}}}Q^{(1)}(\mathbf{x},\mathbf{a})$ has $\Pro$ property. By induction, assume $V^{(n-1)}(\mathbf{x},\mathbf{a})$ has $\Pro$ property. Then $Q^{(n)}$ and $V^{(n)}(\mathbf{x})=\min_{\mathbf{a}\in{\mathcal{A}}}Q^{(n)}(\mathbf{x},\mathbf{a})$ have $\Pro$ property. Therefore, $Q^{(N)}(\mathbf{x},\mathbf{a})$ and $V^{*}(\mathbf{x})=V^{(N)}(\mathbf{x})$ must also possess $\Pro$ property, and $\theta^*(\mathbf{x})=\arg\min_{\mathbf{a}\in{\mathcal{A}}}Q^{(N)}(\mathbf{x},\mathbf{a})$ is monotonic in $\mathbf{x}$.
\end{IEEEproof}

\subsection{Monotonic Policies in Queues States}
\label{sec:StructB}

\subsubsection{Nondecreasing $a_i^*$ in $b_i$}

Let the optimal action be $\mathbf{a}^*=(a_1^*,a_2^*)=\theta^*(\mathbf{x})$. The following theorem shows that the optimal action $a_i^*$ is monotonic in $b_i$, the state of queue being controlled by $a_i$ if the unit costs satisfy a certain condition.
\begin{theorem} \label{theo:LconvexOfImmediate}
If $\xi_o \geq{2\lambda+\eta+\tau}$, then for all $i\in\{1,2\}$ $C(\mathbf{x},\mathbf{a})$ and $Q^{(n)}(\mathbf{x},\mathbf{a})$ are nondecreasing in $b_i$ and $L^{\natural}$-convex in $(b_i,a_i)$, $V^*(\mathbf{x})$ is nondecreasing and $L^{\natural}$-convex in $b_i$, and the optimal action $a^*_i$ is nondecreasing in $b_i$.
\end{theorem}
\begin{IEEEproof}
We define two functions
\begin{equation}
\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})=\tilde{C}_h(\mathbf{y})+C_t(\mathbf{g},\mathbf{a}),
\end{equation}
where $\tilde{C}_h(\mathbf{y})=\sum_{i=1}^{2}h_i(y_i)$ and
\begin{equation}
\tilde{Q}^{(n)}(\mathbf{y},\mathbf{g},\mathbf{a})=\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})+\beta \mathbb{E}_{\mathbf{g}'} \Big[ V_\mathbf{f}^{(n-1)}(\mathbf{y},\mathbf{g}') \Big|\mathbf{g} \Big].
\end{equation}
Here,
\begin{equation}
	V_\mathbf{f}^{(n-1)}(\mathbf{y},\mathbf{g}')=\mathbb{E}_\mathbf{f} \Big[ V^{(n-1)}(\min\{[y_1]^+,L_1\}+f_1,\min\{[y_2]^+,L_2\}+f_2,\mathbf{g}') \Big],
\end{equation}
$\mathbf{y}=(y_1,y_2)$ and $\mathbf{f}=(f_1,f_2)$. It is easy to see that $C(\mathbf{b},\mathbf{g},\mathbf{a})=\tilde{C}(\mathbf{b}-\mathbf{a},\mathbf{g},\mathbf{a})$ and $Q^{(n)}(\mathbf{b},\mathbf{g},\mathbf{a})=\tilde{Q}^{(n)}(\mathbf{b}-\mathbf{a},\mathbf{g},\mathbf{a})$.
Since
\begin{equation}
    \left[ \begin{array}{ccc} b_i-a_i \\ a_i  \end{array} \right]=\left[ \begin{array}{ccc} 1 & -1  \\ 0 & 1  \end{array} \right] \left[ \begin{array}{ccc} b_i \\ a_i  \end{array} \right]=-M_{2,2}^{-1} \left[ \begin{array}{ccc} b_i \\ a_i  \end{array} \right],
\end{equation}
according to Lemma~\ref{lemma:UniTrans}(b), it follows that proving the $L^{\natural}$-convexity of $C(\mathbf{b},\mathbf{g},\mathbf{a})$ and $Q^{(n)}(\mathbf{b},\mathbf{g},\mathbf{a})$ in $(b_i,a_i)$ is equivalent to showing the multimodularity of $\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})$ and $\tilde{Q}^{(n)}(\mathbf{y},\mathbf{g},\mathbf{a})$ in $(y_i,a_i)$. It is also clear that the monotonicity of $C(\mathbf{b},\mathbf{g},\mathbf{a})$ and $Q^{(n)}(\mathbf{b},\mathbf{g},\mathbf{a})$ in $b_i$ is equivalent to the monotonicity of $\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})$ and $\tilde{Q}^{(n)}(\mathbf{y},\mathbf{g},\mathbf{a})$ in $y_i$. See Appendix~\ref{app:LconvexOfImmediate} for the proof of the monotonicity and multimodularity of $\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})$ and $\tilde{Q}^{(n)}(\mathbf{y},\mathbf{g},\mathbf{a})$ in $y_i$ and $(y_i,a_i)$, respectively.

According to Proposition 4.7.3 in \cite{PutermanMDP1994}, $V^*(\mathbf{x})$ is nondecreasing in $b_i$. By Theorem~\ref{theo:PstarProperty} and Proposition~\ref{prop:PropertyDP}, $V^*(\mathbf{x})$ is $L^{\natural}$-convex in $b_i$, and $a_i^*$ is nondecreasing in $b_i$.
\end{IEEEproof}

Note, Theorem~\ref{theo:LconvexOfImmediate} aligns with the existing results in the literature, e.g., the adaptive MIMO transmission control \cite{Djonin2007} and the Markov game modeled adaptive modulation of cognitive radio \cite{Huang2010}. In fact, both of them can be explained by $L^{\natural}$-convexity. In \cite{Djonin2007}, the monotonicity of $a_i^*$ in $b_i$ was shown by the multimodularity in $(b_i,-a_i)$. But
\begin{equation}
    \left[ \begin{array}{ccc} b_i \\ -a_i  \end{array} \right]=\left[ \begin{array}{ccc} 1 & 0 \\ 0 & -1  \end{array} \right] \left[ \begin{array}{ccc} b_i \\ a_i  \end{array} \right]=-M_{2,1}^{-1}\left[ \begin{array}{ccc} b_i \\ a_i  \end{array} \right]
\end{equation}
By Lemma~\ref{lemma:UniTrans}(b), we know that if the a function is multimodular in $(b_i,-a_i)$, then it must be $L^{\natural}$-convex in $(b_i,a_i)$. Consequently, $V^{(n)}(\mathbf{x})$ is integer convex in $b_i$ because $L^{\natural}$-convexity in one dimension is exactly integer convexity\footnote{In \cite{Djonin2007}, integer convexity was used to denote the one dimensional discrete convexity as explained in Lemma~\ref{lemma:LconvexPreserve}(c).}. In \cite{Huang2010}, the monotonicity of $a_i^*$ was shown by the submodularity of $Q^{(n)}$ in $(b_i,a_i)$. But, $Q^{(n)}$ is a function of $b_i-a_i$. According to Definition~\ref{def:Lconvex}, the $L^{\natural}$-convexity of $g(x_1,x_2)=f(x_1-x_2)$ in $(x_1,x_2)$ is equivalent to the submodularity of $g(x_1,x_2)$ in $(x_1,x_2)$. So $Q^{(n)}$ is also $L^{\natural}$-convex in $(b_i,a_i)$.
\subsubsection{Nondecreasing $a_i^*$ in $(b_1,b_2)$}

\begin{figure}[tbp]
	\centering
		\centerline{\scalebox{1}{\input{figures/SupGame.tex}}}
	\caption{Utility matrix of one-stage pure coordination game in the $n$th iteration in DP. $-Q^{(n)}:\mathcal{A}_1\times{\mathcal{A}_2}\rightarrow{\mathbb{R}_{-}}$ is considered the utility function for a fixed $\mathbf{x}$.}
	\label{fig:SupGame}
\end{figure}

We formulate the optimization problem in the $n$th iteration of DP by a 2-player 2-strategy game, which is called one-stage game in Fig.~\ref{fig:SupGame}. Assume that action $a_1$ is taken by player 1, and $a_2$ is taken by player 2. Obviously, it is a pure coordination game where the utility $-Q^{(n)}(\mathbf{x},(a_1,a_2))$ is the same to player 1 and 2.

We prove, in Appendix~\ref{app:TeamGame}, that Fig.~\ref{fig:SupGame} is a supermodular game with utility function $-Q^{(n)}(\mathbf{x},\mathbf{a})$ strictly supermodular in $\mathbf{a}=(a_1,a_2)$ for all $\mathbf{x}$ and $V^{(n-1)}(\mathbf{x}')$ that is $L^{\natural}$-convex in $\mathbf{b}'=(b'_1,b'_2)$. It is proved in \cite{Milgrom1990} that there exists at least one equilibrium $(a_1^*,a_2^*)$ in the form of pure strategy in a supermodular game. Then, we have the following theorem for the monotonicity of the optimal action $a_i^*$ in $\mathbf{b}=(b_1,b_2)$.
\begin{theorem} \label{theo:LconvexOfQ}
If
\begin{enumerate}[(a)]
    \item $\xi_o \geq 2\lambda+\eta+\tau$,
    \item one-stage game (in Fig.~\ref{fig:SupGame}) has two pure strategy equilibria $(0,0)$ and $(1,1)$  for all $\mathbf{x}=(b_1,b_2,g_1,g_2)$ such that $b_i<L_i+1$ for all $i\in\{1,2\}$,
\end{enumerate}
then $C(\mathbf{x},\mathbf{a})$ and $Q^{(n)}(\mathbf{x},\mathbf{a})$ are $L^{\natural}$-convex in $(\mathbf{b},\mathbf{a})=(b_1,b_2,a_1,a_2)$, the optimal value function $V^*(\mathbf{x})$ is $L^{\natural}$-convex in $\mathbf{b}=(b_1,b_2)$ and the optimal action $\mathbf{a}^*=(a_1^*,a_2^*)$ is nondecreasing in $\mathbf{b}=(b_1,b_2)$.
\end{theorem}
The proof is in Appendix~\ref{app:LconvexOfQ}. \hfill\IEEEQED

Here is a corollary of Theorem~\ref{theo:LconvexOfQ}.
\begin{corollary} \label{lemma:BREquiProb}
If
\begin{enumerate}[(a)]
  \item $\xi_o \geq 2\lambda+\eta+\tau$,
  \item $p_1=p_2=0.5$,
  \item $\beta \leq \frac{2(\tau-\lambda)}{\tau+\eta}$,
\end{enumerate}
then Theorem~\ref{theo:LconvexOfQ} holds.
\end{corollary}
The proof is in Appendix~\ref{app:BREquiProb}. \hfill\IEEEQED

We show examples of Theorems~\ref{theo:LconvexOfImmediate} and \ref{theo:LconvexOfQ} in Figs.~\ref{fig:a_b(Mono)1}-\ref{fig:a_bv(Mono)2}. The results are collected by value iteration, a DP algorithm, applied on an NC-TWRC system with Bernoulli symbol arrivals, $5$ queue states and $8$ channel states, i.e., $f_i^{(t)}\sim{\text{Bernoulli}(p_i)}$, $L_i=3$ and $K_i=8$ for all $t$ and $i\in\{1,2\}$. In Fig.~\ref{fig:a_b(Mono)1}, we choose the values of unit costs to make Theorem~\ref{theo:LconvexOfImmediate} hold. As shown in the figure, the optimal action $a_1^*$ and $a_2^*$ are monotonic in $b_1$ and $b_2$, respectively, i.e., $a_i^*$ is nondecreasing in the queue state that is being controlled by $a_i$. In Fig.~\ref{fig:a_b(Mono)2}, we change the value of unit cost $\xi_o$ to breach the condition in Theorem~\ref{theo:LconvexOfImmediate} so that the monotonicity of $a_i^*$ in $b_i$ is not guaranteed. In this case, $a_1^*$ that is not monotonic in $b_1$.

\begin{figure}[t]
	\centering
    \subfigure{\scalebox{0.65}{\input{figures/a_b_NonMono2_1.tex}}}\qquad
    \subfigure{\scalebox{0.65}{\input{figures/a_b_NonMono2_2.tex}}}
	\caption{The optimal action $a_1^*$ (left) and $a_2^*$ (right) vs. $b_1$, the state of queue 1, and $b_2$, the state of queue 2, where $p_1=0.1$, $p_2=0.2$, $\lambda=0.05$, $\tau=1$, $\eta=2$, $\xi_o=4$ and $\beta=0.97$. In this case, $\xi_o \geq 2\lambda+\eta+\tau$. The condition in Theorem~\ref{theo:LconvexOfImmediate} is satisfied. Therefore, $a_1^*$ and $a_2^*$ are nondecreasing in $b_1$ and $b_2$, respectively.}
	\label{fig:a_b(Mono)1}
\end{figure}

\begin{figure}[tbp]
	\centering
    \subfigure{\scalebox{0.65}{\input{figures/a_b_NonMono1_1.tex}}}\qquad
    \subfigure{\scalebox{0.65}{\input{figures/a_b_NonMono1_2.tex}}}
	\caption{The optimal action $a_1^*$ (left) and $a_2^*$ (right) vs. $b_1$, the state of queue 1, and $b_2$, the state of queue 2, where $p_1=0.1$, $p_2=0.2$, $\lambda=0.05$, $\tau=1$, $\eta=2$, $\xi_o=1$ and $\beta=0.97$. In this case, $\xi_o < 2\lambda+\eta+\tau$. Theorem~\ref{theo:LconvexOfImmediate} no longer holds. As can be seen, $a_1^*$ is not monotonic in $b_1$.}
	\label{fig:a_b(Mono)2}
\end{figure}

In Fig.~\ref{fig:a_bv(Mono)1}, we choose the equiprobable symbol arrival rates $p_1=p_2=0.5$ and the unit costs according to Corollary~\ref{lemma:BREquiProb} to make Theorem~\ref{theo:LconvexOfQ} hold. As shown in the figure, the optimal action $a_1^*$ and $a_2^*$ are both nondecreasing in $(b_1,b_2)$. As compared to Fig.~\ref{fig:a_b(Mono)1}, in this case, $a_i^*$ is also monotonic in $b_{-i}$, the queue state that is affected by the message flow and transmission control in the opposite direction, i.e., the queue state that is not controlled by $a_i$. In Fig.~\ref{fig:a_bv(Mono)2}, we switch unit cost $\eta$ from $1$ to $2$ so that Theorem~\ref{theo:LconvexOfQ} no longer holds. In this case, neither $a_1^*$ nor $a_2^*$ is monotonic in $(b_1,b_2)$. But, the condition in Theorem~\ref{theo:LconvexOfImmediate} is satisfied. Therefore, $a_1^*$ and $a_2^*$ are still nondecreasing in $b_1$ and $b_2$, respectively.

\begin{figure}[t]
	\centering
    \subfigure{\scalebox{0.65}{\input{figures/a_bv_equiPMono_1.tex}}} \qquad
    \subfigure{\scalebox{0.65}{\input{figures/a_bv_equiPMono_2.tex}}}
	\caption{The optimal action $a_1^*$ (left) and $a_2^*$ (right) vs. $b_1$, the state of queue 1, and $b_2$, the state of queue 2, where $p_1=p_2=0.5$, $\lambda=0.05$, $\tau=1$, $\eta=1$, $\xi_o=4$ and $\beta=0.97$. In this case, $\xi_o \geq 2\lambda+\eta+\tau$ and $\beta \leq \frac{2(\tau-\lambda)}{\tau+\eta}$. According to Corollary~\ref{lemma:BREquiProb}, Theorem~\ref{theo:LconvexOfQ} holds. Therefore, both $a_1^*$ and $a_2^*$ are nondecreasing in $(b_1,b_2)$.}
	\label{fig:a_bv(Mono)1}
\end{figure}

\begin{figure}[tbp]
	\centering
    \subfigure{\scalebox{0.65}{\input{figures/a_bv_equiPNonMono_1.tex}}} \qquad
    \subfigure{\scalebox{0.65}{\input{figures/a_bv_equiPNonMono_2.tex}}}
	\caption{The optimal action $a_1^*$ (left) and $a_2^*$ (right) vs. $b_1$, the state of queue 1, and $b_2$, the state of queue 2, where $p_1=p_2=0.5$, $\lambda=0.05$, $\tau=1$, $\eta=2$, $\xi_o=4$ and $\beta=0.97$. In this case, $\xi_o \geq 2\lambda+\eta+\tau$ but $\beta > \frac{2(\tau-\lambda)}{\tau+\eta}$. Theorem~\ref{theo:LconvexOfImmediate} holds, while Theorem~\ref{theo:LconvexOfQ} does not. As can be seen,  $a_1^*$ and $a_2^*$ are monotonic in $b_1$ and $b_2$ respectively, but $a_1^*$ is not monotonic in $b_2$.}
	\label{fig:a_bv(Mono)2}
\end{figure}

\subsection{Monotonic Policies in Channel States}
\label{sec:StructG}

The related research work in the existing literature considers the structure of the optimal policy in queue state only, e.g., \cite{Huang2010},\cite{Djonin2007} and \cite{Yang2012}. This section breaks this limitation in that we extend the investigation of the monotonicity to the channel states. The main results are summarized as follows.
\begin{theorem} \label{theo:SubOnChannel}
If
\begin{itemize}
  \item[(a)] $\xi_o \geq 2\lambda+\eta+\tau$,
  \item[(b)] $P_e(g_i)\geq{P_e(g_i+1)}$,
  \item[(c)] $P_{g_ig_i^\prime}$ is first order stochastic nondecreasing in $g_i$,
  \item[(d)] $\beta\leq\frac{P_e(g_i)-P_e(g_i+1)}{\sum_{g'_i}P_{g_ig'_i} ( P_e(g'_i)-P_e(g'_i+1) ) }$.
\end{itemize}
then $C(\mathbf{x},\mathbf{a})$ and $Q^{(n)}(\mathbf{x},\mathbf{a})$ is submodular in $(b_{i},g_{-i},a_{i})$, $V^{*}(\mathbf{x})$ is submodular in $(b_{i},g_{-i})$ and the optimal action $a_i^*$ is nondecreasing in $(b_{i},g_{-i})$.
\end{theorem}
The proof is in Appendix~\ref{app:SubOnChannel}.  \hfill\IEEEQED

In Theorem~\ref{theo:SubOnChannel}, conditions (b)--(d) depend on the fading statistics, the FSMC modeling method and the modulation scheme. In fact, condition (b) and (c) are not hard to satisfy if we adopt the equiprobable partition methods in the FSMCs.
\begin{corollary} \label{lemma:EquiFSMC}
Under assumption A3, if the FSMC of channel $i$ adopts equiprobable partitioning (of the full range of SNR), and channel $i$ experiences slow and flat Rayleigh fading, then condition (b) and (c) in Theorem~\ref{theo:SubOnChannel} are satisfied.
\end{corollary}
The proof is in Appendix~\ref{app:EquiFSMC}.   \hfill\IEEEQED

Finally, condition (d) depends on the modulation scheme, which should be determined in the real applications.

\begin{figure}[t]
	\centering
    \subfigure{\scalebox{0.65}{\input{figures/a_bg_Mono_1.tex}}} \qquad
    \subfigure{\scalebox{0.65}{\input{figures/a_bg_Mono_2.tex}}}
	\caption{The optimal action $a_1^*$ vs. queue state $b_1$ and channel state $g_2$ (left), and $a_2^*$ vs. $b_2$ and $g_1$ (right), where $p_1=0.1$, $p_2=0.2$, $\lambda=0.05$, $\tau=1$, $\eta=2$, $\xi_o=4$ and $\beta=0.95$. Two channels are both Rayleigh fading with $\overline{\gamma}_1=\overline{\gamma}_2=0\si{\decibel}$ and are both modeled by 8-state equiprobable FSMCs. Modulation scheme is BPSK. In this case, $\beta\leq\frac{P_e(g_i)-P_e(g_i+1)}{\sum_{g'_i}P_{g_ig'_i} ( P_e(g'_i)-P_e(g'_i+1) ) }$, and according to Corollary~\ref{lemma:EquiFSMC}, Theorem~\ref{theo:SubOnChannel} holds. Therefore, $a_1^*$ and $a_2^*$ are nondecreasing in $(b_1,g_2)$ and $(b_2,g_1)$, respectively.}
	\label{fig:a_bg(Mono)1}
\end{figure}

\begin{figure}[tbp]
	\centering
    \subfigure{\scalebox{0.65}{\input{figures/a_bg_NonMono_1.tex}}} \qquad
    \subfigure{\scalebox{0.65}{\input{figures/a_bg_NonMono_2.tex}}}
	\caption{The optimal action $a_1^*$ vs. queue state $b_1$ and channel state $g_2$ (left), and $a_2^*$ vs. $b_2$ and $g_1$ (right), where $p_1=0.1$, $p_2=0.2$, $\lambda=0.05$, $\tau=1$, $\eta=2$, $\xi_o=4$ and $\beta=0.95$. Two channels are both Rayleigh fading and are both modeled by 8-state equiprobable FSMCs. But $\overline{\gamma}_1=0\si{\decibel}$ and $\overline{\gamma}_2=3\si{\decibel}$. Modulation scheme is still BPSK. In this case, $\beta\leq\frac{P_e(g_i)-P_e(g_i+1)}{\sum_{g'_i}P_{g_ig'_i} ( P_e(g'_i)-P_e(g'_i+1) ) }$ does not hold for all $g_i$. We can see that $a_1^*$ is not monotonic in $g_2$.}
	\label{fig:a_bg(Mono)2}
\end{figure}

We show examples of Theorem~\ref{theo:SubOnChannel} in Figs.~\ref{fig:a_bg(Mono)1} and \ref{fig:a_bg(Mono)2}. In Fig.~\ref{fig:a_bg(Mono)1}, we use the same system parameters as in Fig.~\ref{fig:a_b(Mono)1} except that the discount factor $\beta$ is switched from $0.97$ to $0.95$ in order to satisfy the inequality in condition (d) of Theorem~\ref{theo:SubOnChannel} . The results are obtained from an NC-TWRC system exchanging BPSK symbols over slow and flat Rayleigh fading channels with average SNR $\overline{\gamma}_1=\overline{\gamma}_2=0\si{\decibel}$. Both FSMCs are $8$-state and adopt equiprobable partition method. In this case, all the conditions in Theorem~\ref{theo:SubOnChannel} are satisfied according to Corollary~\ref{lemma:EquiFSMC}. Therefore, $a_1^*$ is nondecreasing in $(b_1,g_2)$, and $a_2^*$ is nondecreasing in $(b_2,g_1)$. In Fig.~\ref{fig:a_bg(Mono)2}, we switch $\overline{\gamma}_2$ from $0\si{\decibel}$ to $3\si{\decibel}$ to breach condition (d) in Theorem~\ref{theo:SubOnChannel}. In this case, $a_1^*$ is not monotonic in $g_2$. But, since Theorem~\ref{theo:LconvexOfImmediate} still holds, $a_1^*$ and $a_2^*$ are monotonic in $b_1$ and $b_2$, respectively.

\begin{figure}[t]
	\centering
    \subfigure{\scalebox{0.65}{\input{figures/TH_bg_Mono_1.tex}}}  \qquad
    \subfigure{\scalebox{0.65}{\input{figures/TH_bg_Mono_2.tex}}}
	\caption{The optimal threshold $b_{1_{th}}^{*}$ vs. queue state $b_{2}$ and channel state $g_{2}$ (left), and $b_{2_{th}}^{*}$ vs. $b_{1}$ and $g_{1}$ (right), with $p_1=p_2=0.5$, $\lambda=0.05$, $\tau=1$, $\eta=1$, $\xi_o=4$ and $\beta=0.95$. Two channels are both Rayleigh fading with $\overline{\gamma}_1=\overline{\gamma}_2=0\si{\decibel}$ and modeled by $8$-state equiprobable FSMCs. Modulation scheme is BPSK. In this case, Theorem~\ref{theo:SubOnChannel} and \ref{theo:LconvexOfImmediate} hold. Therefore, the optimal threshold $b_{1_{th}}^{*}$ and $b_{2_{th}}^{*}$ are nonincreasing in $(b_2,g_2)$ and $(b_1,g_1)$, respectively.}
	\label{fig:TH(Mono)}
\end{figure}

In Fig.~\ref{fig:TH(Mono)}, we show a monotonic optimal threshold policy when both Theorem~\ref{theo:LconvexOfQ} and Theorem~\ref{theo:SubOnChannel} hold. In this figure, $b_{i_{th}}^{*}$ is the optimal threshold defined by
\begin{equation}
    b_{i_{th}}^{*}(b_{-i},g_1,g_2)=\min\{b_i \colon a_i^*(\mathbf{x})=1\}.
\end{equation}
Because of the monotonicity of $a_i^*$ in $(b_1,b_2,g_{-i})$, $b_{i_{th}}^{*}(b_{-i},g_1,g_2)$ is nonincreasing in $(b_{-i},g_{-i})$. By stacking the $b_{i_{th}}$ for all $(b_{-i},g_1,g_2)$, we can form a vector $\mathbf{b}_{th}$ with the cardinality being $|\B_{-i}|\times|\G_1|\times|\G_2|$ and convert \eqref{eq:obj} to
\begin{align}\label{eq:LConvexOpt}
        &\quad \min_{\mathbf{b}_{th}} J(\mathbf{b}_{th})   \nonumber \\
        &s.t.\ C_i(\mathbf{b}_{th})\leq{0}, \forall{i},
\end{align}
where $J$ could be the objective in \eqref{eq:obj} obtained by a Markov chain\footnote{Each $\mathbf{b}_{th}$ results in a Markov chain with the transition probability being $Pr(\mathbf{x}'|\mathbf{x})=P_{\mathbf{x}\x'}^{\theta_{th}(\mathbf{x})}$, where $\theta_{th}(\mathbf{x})=(\mathcal{I}_{\{b_1\geq b_{1_{th}}(b_2,g_1,g_2)\}},\mathcal{I}_{\{b_2\geq b_{2_{th}}(b_1,g_1,g_2)\}})$.} simulation and $C_i(\mathbf{b}_{th})$ could be the constraint imposed by the monotonicity of $b_{i_{th}}$ in $(b_{-i},g_{-i})$. The method that solves \eqref{eq:LConvexOpt} could be, but not restricted to, a stochastic approximation algorithm, e.g. SPSA \cite{Huang2010}, that has lower complexity than DP and is suitable for online reinforcement learning. We will not discuss the details since it is not the purpose of our work. But, it should be clear that the results derived in this paper can be used for further study on \eqref{eq:LConvexOpt}. They are, in fact, the prerequisites for threshold policy optimization problems.

Note, that the related previous studies usually placed constraints on the environments or the DP functions in order to prove the structure in the optimal policy. For example, in \cite{Huang2010} the submodularity of the state transition probability was proved by assuming uniformly distributed traffic rates, and in \cite{Hoang2008} the strict submodularity of $Q^{(n)}$ in DP iterations was assumed to be preserved by a weight factor in the immediate cost function (However, the exact value of this factor was not given). In contrast, the results in this paper, Theorem~\ref{theo:LconvexOfImmediate}, \ref{theo:LconvexOfQ} and \ref{theo:SubOnChannel}, are essentially given in terms of unit costs and discount factor, the parameters in the MDP model. The practical meaning of them can be interpreted in two ways. If the unit costs and discount factor are adjustable, we can tune them to get a structured optimal policy. If they are given, we can check the sufficient conditions for the existence of a monotonic optimal policy after the MDP modeling. There were some results considering the uniform traffic rates, stochastic dominance of channel transition probabilities and channel modeling and modulation scheme in this paper. We either presented them as corollaries or showed the feasibility in practice by examples.

\section{Conclusion}

This paper studied an MDP modeled transmission control problem in NC-TWRC with random traffic and fading channels. The purpose was to prove the existence of a monotonic optimal transmission policy that minimized symbol delay, queue overflow, transmission power and the downlink transmission error rate in the long run. The monotonicity was established by investigating how certain properties (submodularity, $L^{\natural}$-convexity and multimodularity) of DP varied with the system parameters. This paper differed from the previous studies in two ways. Firstly, the nondecreasing optimal policy was proved to be conditioned on the parameters in the MDP model, e.g., unit costs or discount factor, instead of the constraints placed on the environment of the NC-TWRC system. Secondly, we observed the monotonicity in both queue and channel states instead of queue state only. The results in this paper can be utilized for further studies on how to simplify the optimization processes in DP, which could be useful in realtime control scenarios of NC-TWRC.

\appendices

\section{
\label{app:SubmodularPreserve}

\subsubsection*{Proof of Lemma~\ref{lemma:SubmodularPreserve}(b)}
According to Definition~\ref{def:submodularity}, since
\begin{align}
    &\quad \sum_{i=1}^{m}\alpha_if_i(\mathbf{x}+\mathbf{e}_v)+\sum_{i=1}^{m}\alpha_if_i(\mathbf{x}+\mathbf{e}_w)-\sum_{i=1}^{m}\alpha_if_i(\mathbf{x})-\sum_{i=1}^{m}\alpha_if_i(\mathbf{x}+\mathbf{e}_v+\mathbf{e}_w) \nonumber \\
    &=\sum_{i=1}^{m}\alpha_i\Big( f_i(\mathbf{x}+\mathbf{e}_v)+f_i(\mathbf{x}+\mathbf{e}_w)-f_i(\mathbf{x})-f_i(\mathbf{x}+\mathbf{e}_v+\mathbf{e}_w) \Big)\geq{0}
\end{align}
for all $1\leq{v,w}\leq{n}$ such that $v\neq{w}$, so $\sum_{i=1}^{m}\alpha_if_i(\mathbf{x})$ is submodular in $\mathbf{x}$.   \hfill\IEEEQED

\subsubsection*{Proof of Lemma~\ref{lemma:LconvexPreserve}(a)}
The case when $g$ is $L^{\natural}$-convex can be proved by Lemma $2$ and $3$\footnote{Based on Lemma $2$ and $3$ in \cite{Zipkin2008}, $f(\mathbf{x})=\min_{\alpha}g(\mathbf{x},\alpha)$ is $L^{\natural}$-convex in $\mathbf{x}$ and $\alpha^*(\mathbf{x})=\arg\min_{\alpha}g(\mathbf{x},\alpha)$ is nondecreasing $\mathbf{x}$ if $g$ is $L^{\natural}$-convex in $(\mathbf{x},\alpha)$, where $\mathbf{x}\in\mathbb{Z}^n$ and $\alpha\in{\mathbb{Z}}$.} in \cite{Zipkin2008} through a sequential minimization, i.e., minimizing over the tuples in $\mathbf{y}$ one after another. The case when $g$ is multimodular can be proved by Theorem 1\footnote{$f(\mathbf{x})=\min_{\alpha}g(\mathbf{x},\alpha)$ is multimodular in $\mathbf{x}$ and $\alpha^*(\mathbf{x})=\arg\min_{\alpha}g(\mathbf{x},\alpha)$ is nonincreasing in $\mathbf{x}$ if $g$ is multimodular in $(\mathbf{x},\alpha)$, where $\mathbf{x}\in\mathbb{Z}^n$ and $\alpha\in{\mathbb{Z}}$. } in \cite{Yu2013} in the same way.   \hfill\IEEEQED

\subsubsection*{Proof of Lemma~\ref{lemma:LconvexPreserve}(b)}
Consider the case of $L^{\natural}$-convexity first. According to Definition~\ref{def:Lconvex} and Lemma~\ref{lemma:SubmodularPreserve}(b), $\sum_{i=1}^{m}\alpha_if_i(\mathbf{x}-\zeta\mathbf{1})$ is submodular in $(\mathbf{x},\zeta)$ because of the submodularity of $f_i$ in $(\mathbf{x},\zeta)$. Therefore, $\sum_{i=1}^{m}\alpha_if_i(\mathbf{x})$ is $L^{\natural}$-convex.
In the same way, we can show that $\sum_{i=1}^{m}\alpha_if_i(\mathbf{x})$ is multimodular if $f_i$ is multimodular for all $i$. \hfill\IEEEQED

\subsubsection*{Proof of Lemma~\ref{lemma:LconvexPreserve}(c)}
Consider function $f$ first. Since $\psi(\mathbf{x},\zeta)=f(\mathbf{x}-\zeta\mathbf{1})=h(x_1-x_2)$, according to Definition~\ref{def:Lconvex}, it suffices to show the submodularity of $h$ in $(x_1,x_2)$. But, because of the convexity of $h$,
    \begin{align}
        &\quad h(x_1+1-x_2)+h(x_1-(x_2+1))-h(x_1-x_2)-h(x_1+1-(x_2+1)) \nonumber \\
                &=h(x_1-x_2+1)+h(x_1-x_2-1)-2h(x_1-x_2)\geq{0}.
    \end{align}
By Definition~\ref{def:submodularity}, $h$ is submodular in $(x_1,x_2)$. Therefore, $f(\mathbf{x})=h(x_1-x_2)$ is $L^{\natural}$-convex in $(x_1,x_2)$. Since $g(\mathbf{x})=f(-M_{2,1}\mathbf{x})$, according to Lemma~\ref{lemma:UniTrans}(a), $g(\mathbf{x})$ is multimodular in $(x_1,x_2)$.  \hfill\IEEEQED

\section{
\label{app:LconvexOfImmediate}

Let$i=1$ and consider the monotonicity first. $\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})$ is nondecreasing in $y_1$ because
\begin{align}
    &\quad \tilde{C}(\mathbf{y}+\mathbf{e}_1,\mathbf{g},\mathbf{a})-\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a}) \nonumber \\
        &=h_1(y_1+1)+h_2(y_2)+C_t(\mathbf{g},\mathbf{a})-h_1(y_1)-h_2(y_2)-C_t(\mathbf{g},\mathbf{a}) \nonumber \\
        &=h_1(y_1+1)-h_1(y_1)   \nonumber \\
        &=\begin{cases}
                                \lambda>0 & -1<y_1<L_1 \\
                                \xi_o>0   & y_1=L_1 \\
                                0         & y_1=-1
                              \end{cases}.
\end{align}
$\tilde{Q}^{n}(\mathbf{y},\mathbf{g},\mathbf{a})$ is nondecreasing in $y_1$ because by assuming that $V^{(n-1)}(\mathbf{x}')$ is nondecreasing in $b'_1$
\begin{align}
    &\quad \tilde{Q}^{n}(\mathbf{y}+\mathbf{e}_1,\mathbf{g},\mathbf{a})-\tilde{Q}^{n}(\mathbf{y},\mathbf{g},\mathbf{a}) \nonumber \\
        &=h_1(y_1+1)-h_1(y_2)+\beta \mathbb{E}_{\mathbf{g}'} \Big[ V_\mathbf{f}^{(n-1)}(\mathbf{y}+\mathbf{e}_1,\mathbf{g}')+V_\mathbf{f}^{(n-1)}(\mathbf{y},\mathbf{g}') \Big|\mathbf{g} \Big] \nonumber \\
        &=\begin{cases}
             \lambda+\beta \mathbb{E}_{\mathbf{g}'} \bigg[ \mathbb{E}_\mathbf{f} \Big[ V^{(n-1)}(\tilde{y}_1+1,\hat{y}_2,\mathbf{g}')  \\ \qquad -V^{(n-1)}(\tilde{y}_1,\hat{y}_2,\mathbf{g}') \Big] \bigg| \mathbf{g} \bigg]>0 & -1<y_1<L_1 \\
             \xi_o>0   & y_1=L_1 \\
             0         & y_1=-1
          \end{cases},
\end{align}
where $\tilde{y}_1=y_1+f_1$ and $\hat{y}_2=\min\{[y_2]^+,L_2\}+f_2$.

Then, consider the multimodularity. Since the function is two-dimensional, we use the Proposition 2 in \cite{Zhuang2012} to prove the multimodularity, i.e., A function $f:\mathbb{Z}^2\rightarrow{\mathbb{R}^+}$ is multimodular if and only if it is (1) supermodualr: $\Delta_i\Delta_j f(\mathbf{x})\geq{0}$ and (2) superconex: $\Delta_i f(\mathbf{x}+\mathbf{e}_i) \geq \Delta_i f(\mathbf{x}+\mathbf{e}_j)$ for all $i,j\in\{1,2\}$, where $\Delta_i f(\mathbf{x})=f(\mathbf{x})-f(\mathbf{x}-\mathbf{e}_i)$ and $\mathbf{e}_i\in{\mathbb{Z}^2}$ is $2$-tuple with all zero entries except the $i$th entry being one.

$\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})$ is supermodular in $(y_1,a_1)$ because
\begin{align}
    &\quad \tilde{C}(\mathbf{y}+\mathbf{e}_1,\mathbf{g},\mathbf{a})+\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a}+\mathbf{e}_1)-\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})-\tilde{C}(\mathbf{y}+\mathbf{e}_1,\mathbf{g},\mathbf{a}+\mathbf{e}_1)=0
\end{align}
and superconvex in $(y_1,a_1)$ because
\begin{align}
    &\quad \tilde{C}(\mathbf{y}+\mathbf{e}_1,\mathbf{g},\mathbf{a})-\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})-\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a}+\mathbf{e}_1)+\tilde{C}(\mathbf{y}-\mathbf{e}_1,\mathbf{g},\mathbf{a}+\mathbf{e}_1)  \nonumber \\
        &=h_1(y_1+1)-2h_1(y_1)+h_1(y_1-1) \geq{0},
\end{align}
where the last inequality is because of the convexity of $h_1$. Therefore, $\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})$ is multimodular in $(y_1,a_1)$.

By assuming the monotonicity and $L^{\natural}$-convexity of $V^{(n-1)}(\mathbf{b}',\mathbf{g}')$ in $b'_1$, $\tilde{Q}^{(n)}(\mathbf{y},\mathbf{g},\mathbf{a})$ is supermodular in $(y_1,a_1)$ because
\begin{align}
    &\quad \tilde{Q}^{n}(\mathbf{y}+\mathbf{e}_1,\mathbf{g},\mathbf{a})+\tilde{Q}^{n}(\mathbf{y},\mathbf{g},\mathbf{a}+\mathbf{e}_1)-\tilde{Q}^{n}(\mathbf{y},\mathbf{g},\mathbf{a})-\tilde{Q}^{n}(\mathbf{y}+\mathbf{e}_1,\mathbf{g},\mathbf{a}+\mathbf{e}_1)=0
\end{align}
and superconvex in $(y_1,a_1)$ because
\begin{align} \label{eq:appQueSingle4}
    &\quad \tilde{Q}^{n}(\mathbf{y}+\mathbf{e}_1,\mathbf{g},\mathbf{a})-\tilde{Q}^{n}(\mathbf{y},\mathbf{g},\mathbf{a})-\tilde{Q}^{n}(\mathbf{y},\mathbf{g},\mathbf{a}+\mathbf{e}_1)+\tilde{Q}^{n}(\mathbf{y}-\mathbf{e}_1,\mathbf{g},\mathbf{a}+\mathbf{e}_1)  \nonumber \\
        &=h_1(y_1+1)-2h_1(y_1)+h_1(y_1-1)  \nonumber \\
        &\quad +\beta \mathbb{E}_{\mathbf{g}'} \Big[ V_\mathbf{f}^{(n-1)}(\mathbf{y}+\mathbf{e}_1,\mathbf{g}')-2V_\mathbf{f}^{(n-1)}(\mathbf{y},\mathbf{g}')+V_\mathbf{f}^{(n-1)}(\mathbf{y}-\mathbf{e}_1,\mathbf{g}') \Big|\mathbf{g} \Big] \nonumber \\
        &=\begin{cases}
             \beta \mathbb{E}_{\mathbf{g}'} \bigg[ \mathbb{E}_\mathbf{f} \Big[ V^{(n-1)}(\tilde{y}_1+1,\hat{y}_2,\mathbf{g}')\\
             \qquad\qquad -2V^{(n-1)}(\tilde{y}_1,\hat{y}_2,\mathbf{g}')+V^{(n-1)}(\tilde{y}_1-1,\hat{y}_2,\mathbf{g}') \Big] \bigg| \mathbf{g} \bigg] \geq 0 & 0<y_1<L_1\\
             \lambda+\beta \mathbb{E}_{\mathbf{g}'} \bigg[ \mathbb{E}_\mathbf{f} \Big[ V^{(n-1)}(1+f_1,\hat{y}_2,\mathbf{g}')  \\ \qquad\qquad -V^{(n-1)}(f_1,\hat{y}_2,\mathbf{g}') \Big] \bigg| \mathbf{g} \bigg] \geq 0 & y_1=0 \\
		     \xi_o-\lambda+\beta \mathbb{E}_{\mathbf{g}'} \bigg[ \mathbb{E}_\mathbf{f} \Big[ -V^{(n-1)}(L_1+f_1,\hat{y}_2,\mathbf{g}')  \\
             \qquad\qquad +V^{(n-1)}(L_1-1+f_1,\hat{y}_2,\mathbf{g}') \Big] \bigg| \mathbf{g} \bigg] \geq 0 & y_1=L_1
          \end{cases},
\end{align}
where $\tilde{y}_1=y_1+f_1$ and $\hat{y}_2=\min\{[y_2]^+,L_2\}+f_2$. The inequality in \eqref{eq:appQueSingle4} in the case of $0<y_1<L_1$ is because of the $L^{\natural}$-convexity of $V^{(n-1)}(\mathbf{b}',\mathbf{g}')$ in $b'_1$ and Lemma~\ref{lemma:LconvexPreserve}(d). The inequality in the case of $y_1=0$ is because of the monotonicity of $V^{(n-1)}(\mathbf{b}',\mathbf{g}')$ in $b'_1$. The inequality in the case of $y_1=L_1$ is explained as follows.

Denote $\mathbf{a}^*(\mathbf{x}')=\arg\min_{\mathbf{a}'}Q^{(n-1)}(\mathbf{x}',\mathbf{a}')$ and recall that $V^{(n-1)}(\mathbf{x}')=Q^{(n-1)}(\mathbf{x}',\mathbf{a}^*(\mathbf{x}'))$. Due to the $L^{\natural}$-convexity of $Q^{(n)}(\mathbf{x}',\mathbf{a}')$ in $(b'_1,a'_1)$, $a_1^*(b'_1,b'_2,\mathbf{g}) \geq a_1^*(b'_1-1,b'_2,\mathbf{g}')$. Because of the monotonicity of $V^{(n-2)}$ in $b''_1$, it is easy to show that the lower bound of $-V^{(n-1)}(b'_1,b'_2,\mathbf{g}')+V^{(n-1)}(b'_1-1,b'_2,\mathbf{g}')$ is given by when $\mathbf{a}^*(b'_1,b'_2,\mathbf{g}')=(1,1)$ and $\mathbf{a}^*(b'_1-1,b'_2,\mathbf{g}')=(0,0)$, i.e., we have
\begin{align} \label{eq:appQueSingle5}
    &\quad -V^{(n-1)}(b'_1,b'_2,\mathbf{g}')+V^{(n-1)}(b'_1-1,b'_2,\mathbf{g}')  \nonumber \\
        &=-Q^{(n-1)}(b'_1,b'_2,\mathbf{g}',\mathbf{a}^*(b'_1,b'_2,\mathbf{g}'))+Q^{(n-1)}(b'_1-1,b'_2,\mathbf{g}',\mathbf{a}^*(b'_1-1,b'_2,\mathbf{g}')) \nonumber \\
        &\geq -Q^{(n-1)}(b'_1,b'_2,\mathbf{g}',(1,1))+Q^{(n-1)}(b'_1-1,b'_2,\mathbf{g}',(0,0)) \nonumber \\
        &\geq -C(b'_1,b'_2,\mathbf{g}',(1,1))+C(b'_1-1,b'_2,\mathbf{g}',(0,0)) \nonumber \\
        &\geq -\lambda-\eta(P_e(g'_1)+P_e(g'_2))-\tau \nonumber \\
        &\geq -\lambda-\eta-\tau,
\end{align}
where last inequality is by knowing $P_e(g'_i)\leq{0.5}, \forall{i}\in\{1,2\}$. Since $\xi_o \geq{2\lambda+\eta+\tau}$, we have the inequality in the case of $y_1=L_1$ in \eqref{eq:appQueSingle4}.

Therefore, $\tilde{Q}^{(n)}(\mathbf{y},\mathbf{g},\mathbf{a})$ is $L^{\natural}$-convex in $(y_1,a_1)$.

In the case of $i=2$, the $L^{\natural}$-convexity of $\tilde{C}(\mathbf{y},\mathbf{g},\mathbf{a})$ and $\tilde{Q}^{(n)}(\mathbf{y},\mathbf{g},\mathbf{a})$ in $(y_2,a_2)$ can be prove in the same way.   \hfill\IEEEQED

\section{
\label{app:TeamGame}
$Q^{(n)}(\mathbf{x},\mathbf{a})$ is strictly submodular in $\mathbf{a}$ because
\begin{align} \label{eq:TeamGameS}
    &\quad Q^{(n)}(\mathbf{x},(1,0))+Q^{(n)}(\mathbf{x},(0,1))-Q^{(n)}(\mathbf{x},(0,0))-Q^{(n)}(\mathbf{x},(1,1))  \nonumber \\
        &=\tau+\beta \mathbb{E}_{\mathbf{g}'} \Big[ V_\mathbf{f}^{(n-1)}(b_1-1,b_2,\mathbf{g}')+V_\mathbf{f}^{(n-1)}(b_1,b_2-1,\mathbf{g}') \nonumber \\
        &\qquad -V_\mathbf{f}^{(n-1)}(b_1,b_2,\mathbf{g}')-V_\mathbf{f}^{(n-1)}(b_1-1,b_2-1,\mathbf{g}') \Big|\mathbf{g} \Big] \nonumber \\
        &= \begin{cases}
		      \tau+\beta \mathbb{E}_{\mathbf{g}'} \Big[ \mathbb{E}_\mathbf{f}[ V^{(n-1)}(\tilde{b}_1-1,\tilde{b}_2,\mathbf{g}')\\
                \quad +V^{(n-1)}(\tilde{b}_1,\tilde{b}_2-1,\mathbf{g}')-V^{(n-1)}(\tilde{b}_1,\tilde{b}_2,\mathbf{g}')\\
                \qquad -V^{(n-1)}(\tilde{b}_1-1,\tilde{b}_2-1,\mathbf{g}') ]\Big|\mathbf{g} \Big]>0 & -1<b_i-a_i<L_i+1,\forall{i}\in{\{1,2\}}\\
		      \tau>0 & otherwise
	       \end{cases},
\end{align}
where $\tilde{b}_i=b_i+f_i$. In \eqref{eq:TeamGameS}, the inequality in the case of $-1<b_i-a_i<L_i+1,\forall{i}\in{\{1,2\}}$ is because of the $L^{\natural}$-convexity of $V^{(n-1)}(\mathbf{b}',\mathbf{g}')$ in $\mathbf{b}'$. Therefore, $-Q^{(n)}(\mathbf{x},\mathbf{a})$ is strictly supermodular in $\mathbf{a}$. According to the definition in \cite{Milgrom1990}, the game is supermodular.
  \hfill\IEEEQED

\section{
\label{app:LconvexOfQ}

$C_{h}(\mathbf{b},\mathbf{a})$ is $L^{\natural}$-convex in $(\mathbf{b},\mathbf{a})$ because of the convexity of $h_i$, and $C_{t}(\mathbf{g},\mathbf{a})$ is $L^{\natural}$-convex in $(\mathbf{b},\mathbf{a})$ because
\begin{align} \label{eq:appImmLconvex1}
    &\quad C_{t}(\mathbf{g},(1,0))+C_{t}(\mathbf{g},(0,1))-C_{t}(\mathbf{g},(0,0))-C_{t}(\mathbf{g},(1,1))  \nonumber \\
        &=\eta P_e(g_2)+\tau+\eta P_e(g_1)+\tau-\eta(P_e(g_1)+P_e(g_2))-\tau \nonumber \\
        &=\tau >0.
\end{align}
Note, since $\mathbf{a}\in\{0,1\}^2$, according to Proposition 2\footnote{A function $f\colon\mathbb{Z}^2\rightarrow{\mathbb{R}}$ is $L^{\natural}$-convex if and only if it is (1) submodular: $\Delta_i\Delta_j f(\mathbf{x})\leq{0}$ and (2) subconex: $\Delta_i f(\mathbf{x}+\mathbf{e}_i) \geq \Delta_i f(\mathbf{x}-\mathbf{e}_j)$ for all $i,j\in\{1,2\}$, where $\Delta_i f(\mathbf{x})=f(\mathbf{x})-f(\mathbf{x}-\mathbf{e}_i)$ and $\mathbf{e}_i\in{\mathbb{Z}^2}$ is $2$-tuple with all zero entries except the $i$th entry being one.} in \cite{Zhuang2012}, the submodularity by \eqref{eq:appImmLconvex1} is sufficient to show the $L^{\natural}$-convexity of $C_{t}(\mathbf{g},\mathbf{a})$ in $(\mathbf{b},\mathbf{a})$. Therefore, by Lemma~\ref{lemma:LconvexPreserve}(b), $C$ is $L^{\natural}$-convex in $(\mathbf{b},\mathbf{a})$.

Then, consider the $L^{\natural}$-convexity of $Q$ in $(\mathbf{b},\mathbf{a})$. Let $BR_i(a_{-i})=\arg\min_{a_{i}}Q^{(n)}(\mathbf{x},(a_i,a_{-i}))$. Equilibria $(0,0),(1,1)$ implies $BR_i(a_{-i})=a_{-i}$, i.e., $a_1=a_2$. Consider
\begin{align} \label{eq:appLconvexOfQ1}
    &\quad Q^{(n)}(\mathbf{b},\mathbf{g},(a_1,a_1))   \nonumber \\
    &=\tilde{C}_h(\mathbf{b}-a_1\mathbf{1})+a_1 \bigg( \eta(P_e(g_1)+P_e(g_2))+\tau \bigg) +\beta \mathbb{E}_{\mathbf{g}'} \Big[ V_\mathbf{f}^{(n-1)}(\mathbf{b}-a_1\mathbf{1},\mathbf{g}') \Big|\mathbf{g} \Big].
\end{align}
$Q^{(n)}(\mathbf{x},(a_1,a_1))$ is $L^{\natural}$-convex in $(\mathbf{b},a_1)$ since: When $b_i-a_1<L_i+1$ for all ${i\in\{1,2\}}$, $Q^{(n)}$ is $L^{\natural}$-convex in $(\mathbf{b},a_1)$ because of the $L^{\natural}$-convexity of $V^{(n-1)}$ in $\mathbf{b}'$ and Lemma~\ref{lemma:LconvexPreserve}(d) and (e); When $b_i-a_1=L_i+1$ for either $i=1$ or $i=2$, the $L^{\natural}$-convexity of $Q^{(n)}$ can be shown in the same way as in Appendix~\ref{app:LconvexOfImmediate} under condition $\xi_o\geq{2\lambda+\tau+\eta}$. By Theorem~\ref{theo:PstarProperty} and Proposition~\ref{prop:PropertyDP}, $V^*(\mathbf{x})$ is $L^{\natural}$-convex in $\mathbf{b}$ and the optimal action $\mathbf{a}^*$ is nondecreasing in $\mathbf{b}$.     \hfill\IEEEQED

\section{
\label{app:BREquiProb}
We just need to show that condition (b) in Theorem~\ref{theo:LconvexOfQ} is satisfied. Let $b_i-a_i<L_i+1$ for all $i\in\{1,2\}$. It suffices to show $BR_i(a_{-i})=a_{-i}$ for all $i\in\{1,2\}$ in order to prove equilibria $(0,0),(1,1)$ in Theorem~\ref{theo:LconvexOfQ}. Because the game has strictly supermodular utility, $BR_i(a_{-i}+1)>BR_i(a_{-i})$. So $BR_i(1)=1$, if we can prove $BR_i(0)=0$. By knowing that $p_1=0.5$, we can show that
\begin{align}
    &\quad Q^{(n)}(\mathbf{b},\mathbf{g},(1,0))-Q^{(n)}(\mathbf{b},\mathbf{g},(0,0)) \nonumber \\
    &=\begin{cases}
          -\lambda+\tau+\eta P_e(g_1) \\
          \quad+0.5\beta \Big( V(b_1-1,\hat{b}_2),\mathbf{g}')-V(b_1+1,\hat{b}_2),\mathbf{g}')\Big) \geq{0}  & 0<b_1<L_1+1 \\
          -\lambda+\tau+\eta P_e(g_1) \geq{0}  & \text{otherwise}
      \end{cases},
\end{align}
where $\hat{b}_2=\min\{[b_2]^+,L_2\}+f_2$ and the inequality in the case when $0<b_1<L_1+1$ is because that, by a similar approach as in \eqref{eq:appQueSingle5}, we can show that
\begin{align} \label{eq:appBREquiProb2}
    &\quad V^{(n-1)}(b'_1-1,b'_2,\mathbf{g}')-V^{(n-1)}(b'_1+1,b'_2,\mathbf{g}') \nonumber \\
    &=Q^{(n-1)}(b'_1-1,b'_2,\mathbf{g}',\mathbf{a}^*(b'_1-1,b'_2,\mathbf{g}'))-Q^{(n-1)}(b'_1+1,b'_2,\mathbf{g}',\mathbf{a}^*(b'_1+1,b'_2,\mathbf{g}')) \nonumber \\
    &\geq  C(b'_1-1,b'_2,\mathbf{g}',(0,0))-C(b'_1+1,b'_2,\mathbf{g}',(1,1))  \nonumber \\
    &= -\tau-\eta(P_e(g'_1)+P_e(g'_2)) \nonumber \\
    &\geq  -\tau-\eta
\end{align}
and the condition $\beta\leq\frac{2(\tau-\lambda)}{\tau+\eta}$.

Similarly, we can show $Q^{(n)}(\mathbf{b},\mathbf{g},(0,1))-Q^{(n)}(\mathbf{b},\mathbf{g},(0,0))\geq{0}$ in the case when $p_2=0.5$. So, $BR_i(a_{-i})=a_{-i}$. \hfill\IEEEQED

\section{
\label{app:SubOnChannel}
Let $i=2$. $C(\mathbf{x},\mathbf{a})$ is submodular in $(b_2,g_1,a_2)$ because
\begin{align} \label{eq:appChan1}
    &\quad C(\mathbf{b}+\mathbf{e}_2,\mathbf{g},\mathbf{a})+C(\mathbf{b},\mathbf{g},\mathbf{a}+\mathbf{e}_2)-C(\mathbf{b},\mathbf{g},\mathbf{a})-C(\mathbf{b}+\mathbf{e}_2,\mathbf{g},\mathbf{a}+\mathbf{e}_2)  \nonumber \\
        &=h_2(b_2+1-a_2)+h_2(b_2-a_2-1)-2h_2(b_2-a_2)\geq{0},
\end{align}
\begin{align} \label{eq:appChan2}
    &\quad C(\mathbf{b}+\mathbf{e}_2,\mathbf{g},\mathbf{a})+C(\mathbf{b},\mathbf{g}+\mathbf{e}_1,\mathbf{a})-C(\mathbf{b},\mathbf{g},\mathbf{a})-C(\mathbf{b}+\mathbf{e}_2,\mathbf{g}+\mathbf{e}_1,\mathbf{a})  \nonumber \\
        &=h_2(b_2+1-a_2)+C_t(\mathbf{g},\mathbf{a})+h_2(b_2-a_2)+C_t(\mathbf{g}+\mathbf{e}_1,\mathbf{a})  \nonumber \\
        &\qquad  -h_2(b_2-a_2)-C_t(\mathbf{g},\mathbf{a})-h_2(b_2+1-a_2)-C_t(\mathbf{g}+\mathbf{e}_1,\mathbf{a})=0,
\end{align}
\begin{align} \label{eq:appChan3}
    &\quad C(\mathbf{b},\mathbf{g},\mathbf{a}+\mathbf{e}_2)+C(\mathbf{b},\mathbf{g}+\mathbf{e}_1,\mathbf{a})-C(\mathbf{b},\mathbf{g},\mathbf{a})-C(\mathbf{b},\mathbf{g}+\mathbf{e}_1,\mathbf{a}+\mathbf{e}_2)  \nonumber \\
        &=\eta (a_2+1) Pe(g_1)+\eta a_2 Pe(g_1+1)-\eta a_2 Pe(g_1)-\eta(a_2+1) Pe(g_1+1)   \nonumber \\
        &=\eta (P_e(g_1)-P_e(g_1+1))\geq{0}.
\end{align}

By assuming the submodularity of $V^{(n-1)}(\mathbf{b}',\mathbf{g}')$ in $(b'_2,g'_1)$, $Q^{(n)}(\mathbf{x},\mathbf{a})$ is submodular in $(b_2,g_1,a_2)$ because
\begin{align} \label{eq:appChan4}
    &\quad Q^{(n)}(\mathbf{b}+\mathbf{e}_2,\mathbf{g},\mathbf{a})+Q^{(n)}(\mathbf{b},\mathbf{g},\mathbf{a}+\mathbf{e}_2)-Q^{(n)}(\mathbf{b},\mathbf{g},\mathbf{a})-Q^{(n)}(\mathbf{b}+\mathbf{e}_2,\mathbf{g},\mathbf{a}+\mathbf{e}_2)  \nonumber \\
        &=h_2(b_2+1-a_2)+h_2(b_2-a_2-1)-2h_2(b_2-a_2) \nonumber \\
        &\qquad +\beta \mathbb{E}_{\mathbf{g}'} \Big[ V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2+1-a_2,\mathbf{g}')+V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2-a_2-1,\mathbf{g}') \nonumber \\
        &\qquad\qquad  -2V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2-a_2,\mathbf{g}') \Big|\mathbf{g} \Big] \geq{0},
\end{align}
\begin{align} \label{eq:appChan5}
    &\quad Q^{(n)}(\mathbf{b}+\mathbf{e}_2,\mathbf{g},\mathbf{a})+Q^{(n)}(\mathbf{b},\mathbf{g}+\mathbf{e}_1,\mathbf{a})-Q^{(n)}(\mathbf{b},\mathbf{g},\mathbf{a})-Q^{(n)}(\mathbf{b}+\mathbf{e}_2,\mathbf{g}+\mathbf{e}_1,\mathbf{a})  \nonumber \\
        &= \beta \bigg( \mathbb{E}_{\mathbf{g}'} \Big[ V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2+1-a_2,\mathbf{g}') \nonumber \\
        &\qquad -V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2-a_2,\mathbf{g}') \Big|\mathbf{g} \Big] - \mathbb{E}_{(\mathbf{g}+\mathbf{e}_1)'} \Big[ V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2+1-a_2,\mathbf{g}') \nonumber \\
        &\qquad\qquad -V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2-a_2,(\mathbf{g}+\mathbf{e}_1)') \Big|(\mathbf{g}+\mathbf{e}_1) \Big] \bigg) \geq{0},
\end{align}
\begin{align} \label{eq:appChan6}
    &\quad Q^{(n)}(\mathbf{b},\mathbf{g},\mathbf{a}+\mathbf{e}_2)+Q^{(n)}(\mathbf{b},\mathbf{g}+\mathbf{e}_1,\mathbf{a})-Q^{(n)}(\mathbf{b},\mathbf{g},\mathbf{a})-Q^{(n)}(\mathbf{b},\mathbf{g}+\mathbf{e}_1,\mathbf{a}+\mathbf{e}_2)  \nonumber \\
        &=\eta (P_e(g_1)-P_e(g_1+1))+ \beta \mathbb{E}_{\mathbf{g}'} \Big[ V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2-1,\mathbf{g}') \nonumber \\
        &\qquad -V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2,\mathbf{g}') \Big|\mathbf{g} \Big] - \mathbb{E}_{(\mathbf{g}+\mathbf{e}_1)'} \Big[ V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2-1,(\mathbf{g}+\mathbf{e}_1)') \nonumber \\
        &\qquad\qquad  -V_\mathbf{f}^{(n-1)}(b_1-a_1,b_2,(\mathbf{g}+\mathbf{e}_1)') \Big|(\mathbf{g}+\mathbf{e}_1) \Big] \geq{0}.
\end{align}
The inequality in \eqref{eq:appChan4} is because of the convexity of $h_2$ and the $L^{\natural}$-convexity of $V^{(n-1)}(\mathbf{b}',\mathbf{g}')$ in $b'_2$ under condition $\xi_o\geq 2\lambda+\eta+\tau$. The inequality in \eqref{eq:appChan5} is because of the submodularity of $V^{(n-1)}(\mathbf{b}',\mathbf{g}')$ in $(b'_2,g'_1)$ and the first order stochastic monotonicity of $P_{g_ig_i^\prime}$ in $g_i$. The last inequality in \eqref{eq:appChan6} is explained as follows.

By using a similar approach as in \eqref{eq:appQueSingle5}, we can show that
\begin{align} \label{eq:appChan7}
    &\quad V^{(n-1)}(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}')+V^{(n-1)}(\mathbf{b}',\mathbf{g}'+\mathbf{e}_1)-V^{(n-1)}(\mathbf{b}',\mathbf{g}')-V^{(n-1)}(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}'+\mathbf{e}_1)  \nonumber \\
        &=Q^{(n-1)}(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}',\mathbf{a}^*(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}'))+Q^{(n-1)}(\mathbf{b}',\mathbf{g}'+\mathbf{e}_1,\mathbf{a}^*(\mathbf{b}',\mathbf{g}'+\mathbf{e}_1)) \nonumber \\
        &\qquad -Q^{(n-1)}(\mathbf{b}',\mathbf{g}',\mathbf{a}^*(\mathbf{b}',\mathbf{g}'))-Q^{(n-1)}(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}'+\mathbf{e}_1,\mathbf{a}*(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}'+\mathbf{e}_1)) \nonumber \\
        &\geq Q^{(n-1)}(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}',\mathbf{a}^*(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}'))+Q^{(n-1)}(\mathbf{b}',\mathbf{g}'+\mathbf{e}_1,\mathbf{a}^*(\mathbf{b}',\mathbf{g}'+\mathbf{e}_1)) \nonumber \\
        &\qquad -Q^{(n-1)}(\mathbf{b}',\mathbf{g}',\mathbf{a}^*(\mathbf{b}',\mathbf{g}'+\mathbf{e}_1))-Q^{(n-1)}(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}'+\mathbf{e}_1,\mathbf{a}^*(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}')) \nonumber \\
        &\geq Q^{(n-1)}(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}',(0,0))+Q^{(n-1)}(\mathbf{b}',\mathbf{g}'+\mathbf{e}_1,(1,1)) \nonumber \\
        &\qquad -Q^{(n-1)}(\mathbf{b}',\mathbf{g}',(1,1))-Q^{(n-1)}(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}'+\mathbf{e}_1,(0,0)) \nonumber \\
        &\geq C(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}',(0,0))+C(\mathbf{b}',\mathbf{g}'+\mathbf{e}_1,(1,1))  \nonumber \\
        &\qquad -C(\mathbf{b}',\mathbf{g}',(1,1))-C(\mathbf{b}'-\mathbf{e}_2,\mathbf{g}'+\mathbf{e}_1,(0,0)) \nonumber \\
        &=\eta (P_e(g'_1+1)-P_e(g'_1)).
\end{align}
Because of the condition $\beta\leq\frac{P_e(g_i)-P_e(g_i+1)}{\sum_{g'_i}P_{g_ig'_i} ( P_e(g'_i)-P_e(g'_i+1) ) }$, we have the inequality in \eqref{eq:appChan6}.

Similarly, we can show that Theorem~\ref{theo:SubOnChannel} holds for $i=1$. Therefore, by Proposition~\ref{prop:PropertyDP} and Theorem~\ref{theo:PstarProperty}, $V^{*}(\mathbf{x})$ is submodular in $(b_{i},g_{-i})$ and the optimal action $a_i^*$ is nondecreasing in $(b_{i},g_{-i})$.  \hfill\IEEEQED

\section{
\label{app:EquiFSMC}

In an equiprobable partition Rayleigh fading FSMC, $P_e(g_i)$ is nonincreasing in $g_i$, i.e., $P_e(g_i) \geq P_e(g_i+1)$. Because of slow and flat fading assumption, the channel transitions can be worked out by level crossing rate (LCR) \cite{Sadeghi2008} and only happens between adjacent states, i.e., $g'_i\in\{g_i-1, g_i, g_i+1\}$. Further, $P_{gg'}=P_{g'g}$, and $P_{gg'}\ll{P_{gg}}$ for all $g'\neq{g}$. According to Definition~\ref{def:1stStoDom}, for nondecreasing $u$, $P_{g_ig_i^\prime}$ is first order stochastic nondecreasing in $g_i$ because
\begin{align}
        &\quad \sum_{(g_i+1)'}P_{(g_i+1)(g_i+1)'}u \Big( (g_i+1)' \Big)-\sum_{g'_i}P_{g_ig'_i}u(g'_i) \nonumber \\
        &\geq (1-2P_{g_ig_i+1}) \Big( u(g_i+1)-u(g_i) \Big) \geq 0,
\end{align}
where $1-2P_{g_ig_i+1}\geq{0}$ is because $P_{gg'}\ll{P_{gg}}$ and $\sum_{g'}P_{gg'}=1$.   \hfill\IEEEQED

redpajama_set_name: RedPajamaArXiv


text:
David Warner and wife Candice welcome baby girl, share beautiful first photos
David and Candice Warner welcomed their third daughter together. Source: Instagram/Candice Warner.
David Warner and his wife Candice have welcomed a baby girl together and shared a stream of loving family photos from hospital to celebrate the news.
The cricket star – who already shares two daughters, Ivy Mae, two, and four-year-old Indi Rae, with Candice – shared his happiness and pride on Instagram following the birth late on Sunday night, before confirming they have called their newborn girl Isla Rose.
The couple are believed to have welcomed their daughter at the exclusive Lindo Wing at London's St Mary's Hospital – the same hospital the Duchess of Cambridge welcomed all three of her children.
"We welcomed our newest family member Isla Rose Warner at 10:30pm late last night. @candywarner1 was absolutely amazing," the 32-year-old wrote on the social media site, alongside a photo of Candice, 34, cradling Isla in her arms, with his other two daughters cuddling up to her in a lovely family shot.
https://www.instagram.com/p/BzXnMSFJJQD/
"Mum and Bub doing very well and her big sisters are over the moon. #prouddad."
And Candice added her own photo with David joining in for the shot and thanked her husband for his constant support and love in a moving message.
https://www.instagram.com/p/BzXnR77h9Gr/
"Welcome to the world our gorgeous Isla Rose Warner. Born June 30th at 10:30pm. Our little family is now complete. Ivy and Indi are so proud of their sister. @davidwarner31 Your support was and is amazing. Isla we love you. #blessed," she wrote.
The couple also added candid snaps of their daughters meeting their youngest sister on their Instagram stories, before David added a close up of little Isla Rose lying in her hospital cot.
Little Isla Rose was born on June 30. Source: Instagram/David Warner.
Poking fun at her husband, Candice also shared a snap of him fast asleep by her bedside and joked: "It's hard work having a baby darling! Long day."
More snaps show both Ivy and Indi bending down to kiss their sister on the cheek, clearly besotted with her already.
Candice poked fun at her husband as he fell asleep at her bedside. Source: Instagram/Candice Warner.
And fans rushed to congratulate the couple on the newest addition to their family, with one commenting: "Hugest congrats to you all!!! Shes beautiful," while another added: "Congratulations! Surrounded by such beautiful girls, can't wait to meet her."
MAFS stars Jules and Cam added their voices to the messages too, with Jules writing:"Congratulations xx," and Cam adding: "Congratulations mate! Magic x."
Ivy and Indi looked besotted with their baby sister. Source: Instagram/Candice Warner.
The couple confirmed they were expecting at the very end of 2018, with Candice sharing nine happy photographs of her children and husband alongside the announcement.
Read more: David and Candice Warner make exciting baby announcement
"Being together has made us into the family we are today. We are so grateful for all the love and support everyone has shown us this year," the model said at the time. "It is with a full heart that @davidwarner31 & I would like to share with you that in 2019 our family of 4 will become a family of 5.
https://www.instagram.com/p/BsCnh0ABmrG/
"We have another beautiful baby joining our family. We are so thrilled! We wish everyone a Happy new year."
Do you have a message for David and Candice? Do you like their chosen baby name?
CelebrityNewsMedia

redpajama_set_name: RedPajamaCommonCrawl


text:
Home/All/3bs Fidelity Launches India's First Tech Accelerator
3bs Fidelity Launches India's First Tech Accelerator
raihan Send an email 2 weeks ago
With the launch of the first Indian tech accelerator, the 3bs fidelity group has set out to bring technology and investors together. They are also looking to help entrepreneurs create innovative business models and grow their companies. The startup accelerator, which is based in Mumbai, India, was launched earlier this year and is already attracting funding from major tech firms including Facebook and Google. However, it's still early days, and there are a number of challenges ahead.
Delhivery is one of the few startups that digitizes the logistics industry. It works with leading enterprises in the Indian market. The company serves over 17,500 zip codes and 2,300 Indian cities. They work with all of the country's largest e-commerce companies, offering a full suite of logistics services.
Their latest funding round was led by Boston-based investment firm Fidelity. SoftBank Vision Fund, Tiger Global, and Carlyle Group also participated. This makes the startup's valuation above $3 billion.
SALT is another startup that offers a digital-first payment platform. SALT's product enables consumers to make payments easily across countries. In October, the company raised a $500,000 seed round. Now, the startup is moving into an end-to-end automated platform.
RecordBook is a SaaS-based application. It helps digitize workflows and data. The startup has offices in Bangalore and Hyderabad. RecordBook is available in both English and local languages.
InsureMyTeam is a health benefits platform for corporations in India. It covers traditional medical expenses, as well as unlimited consultations. Its founders have experience in healthcare, insurance, and sales. The company has posted $16,000 in revenue over the last five months.
The burgeoning logistics industry is a beast to reckon with. Hence, the need for a slew of start-ups to fill the many shoes that should be. To help out, a slew of VCs and angels have stepped up to the plate. One of these is Delhivery, a start-up that offers a full suite of transportation services in over 2,300 Indian cities. Unlike other unicorns of the road, Delhivery aims to be a player rather than just a one man show. Moreover, the company has a strong customer base, which includes some hefty sized companies. Hence, the need for a robust go-to-market strategy has been identified.
The market for logistics and delivery services is worth a trillion dollars or so. And while there's no shortage of trucking firms and online couriers, Delhivery has managed to stand out from the crowd by offering a suite of logistical services. They also have a bevy of customers including all the big e-commerce players, as well as small and medium enterprises.
As a bonus, they manage to keep their head in the game by providing the best customer service in the industry. In addition, they're able to keep costs down by leveraging technology and efficiencies. One of the more compelling advantages of the company's business model is their ability to offer customers a one-stop shop for all of their logistics needs. This includes all of the aforementioned services and more, all under the same umbrella.
Their latest round of funding is in the form of $277 million. This includes an oh-so-pretty-sweet $100 million investment from FedEx Express, the ecommerce behemoth's delivery arm. The company specializes in a number of niches such as food delivery, retail, and e-commerce.
raihan
Wisetack 45m Series Azevedotechcrunch
A Recap of Elon Musk's Appearance von "Good Time" on YouTube
Can You Buy Viagra Online in Canada?
Beau Vigne Hero Proprietary Red Napa Valley From the Vintner's Collective
An Overview of Indian 75m
Amazon's MiniTV Coming to India
What Does an Interior Designer Do?
10 advantages of wearing a coat in winter
How Does a Company Logo Influence Customers' Purchasing Decisions?
The Role of Customer Support in White Label Facebook Ads
Navigating the Business Landscape in the UK – Kavan Choksi
Mydailypapers © Copyright 2023, All Rights Reserved


text:
Q: How to calculate the horizontal (or vertical) projection in MATLAB? I'm extracting frames (5 frames) from a video (car1.mp4). After that displaying the num of rows (and columns).
And then calculating the sum of pixel values of rows and columns of each frame. Finally plotting the graph between the number of columns (or rows) vs magnitude. Below is my code:
clear all
close all
clc

video=VideoReader('car1.mp4');
numFrames = video.NumberOfFrames;

for i = 1:1:5
    frames = read(video,i);
    imwrite(frames,['image' int2str(i), '.jpg'])
    frames = imresize(frames,[100 150]);

    sz = size(frames);
    numRows = sz(1);
    disp(numRows)
    numCols = sz(2);
    disp(numCols)

    rm = numRows*255;
    for j = 1:numRows
        sumr(j)=0;
        for k = 1:numCols
            pixels1 = impixel(frames,k,j);
            sumr(j)=sumr(j)+pixels1(1);
        end
    end
    s1 = rm./sumr;
    plot(s1)
    xlabel({'Horizontal Projection','(no. of columns)'})
    ylabel('Magnitude')

    rc = numCols*255;
    for u = 1:numCols
        sumc(u)=0;
        for v = 1:numRows
            pixels2 = impixel(frames,v,u);
            sumc(u)=sumc(u)+pixels2(1);
        end
    end
    s2 = rc./sumc;
    plot(s2)
    xlabel({'Vertical Projection','(no. of rows)'})
    ylabel('Magnitude')

 end

The main problem is, there are five frames extracting from the video but it shows output (plot between projection vs magnitude) of only one frame. I'm using for loop so that it shows each and every frame's output (plot between projection vs magnitude), but not showing. And the other problem is why it shows only one projection either Horizontal projection or Vertical projection?
Thanks in advance:)

redpajama_set_name: RedPajamaStackExchange


Our Visual Identity represents our 'brand philosophy', 'brand being' and 'our approach'. The blank area in the Visual Identity represents 'our approach', which is to approach projects with a blank canvas. This enables us to come up with insights, ideas and strategies that translate to innovative and profound solutions.
The multi-colours represent our 'brand philosophy' and 'brand being' Our 'brand being' is passion, creative and fun, intrinsic to who we are.
Our culture flows down from our 'brand being', intrinsic to who we are.
'Creative' because we strive to come up with solutions which are fresh and futuristic. It is good to follow a process, but the freedom to go beyond your boundaries, explore and generate new ideas is what creates innovative solutions.
We want our team to have 'Fun' while delivering solutions to our clients. We also want our clients to have fun working with us.
You will find creators, innovators, executors and deal makers. Some introverts, geeks and stars. People from various backgrounds form our team.
However, you will find 3 things in common; Passion, Creative and Fun.
We do this by assigning roles which people love, giving them freedom to be adventurous and explore possibilities and providing an environment where they can be self-expressed and have fun. We also offer flexible timings to employees, at the same time holding them accountable for deliveries.


How are you doing? Well it's November! That means there's pretty much two whole months left before the Christmas Holidays. I hope that you had a fantastic and safe Halloween. Did you do anything exciting? I took my daughter Trick Or Treatin' and she was dressed up as Doc Mc.Stuffins. Lol. Any who today I will be sharing this beautiful polish from Nina Ultra Pro. See more after the jump!
Cobalt is a bright and rich jelly cobalt blue polish. This is one of those Cobalt polishes that does have that strong smell to it. The formula was smooth but of course sheer with the first coat because it is a jelly polish with good coverage that built nicely. Shown is three thin coats with a top coat.
Nina Ultra Pro polishes can be found at your Sally's Beauty for $4.49. Do you own any Nina Ultra Pro polishes? Do you like this one? Let's chat in the comments down below!
Such a gorgeous blue!! It looks great on you.


text:
Feds Want to Ban Ghislaine Maxwell From Claiming Epstein Victimized Her
'BASELESS'
Prosecutors have asked a judge to prevent the socialite from claiming that she too was a victim of sex-trafficker Jeffrey Epstein as a defense in her case.
Kate Briquelet
Senior Reporter
Published Nov. 12, 2021 5:53PM ET
Laura Cavanaugh/Getty Images
Prosecutors in Ghislaine Maxwell's criminal case have asked a judge to ban the British socialite from claiming that she too was a victim of wealthy sex-trafficker Jeffrey Epstein as a possible defense at trial, new court filings reveal.
Maxwell, 59, is charged with grooming and abusing four underage girls for Epstein, her former boyfriend and employer, in the 1990s and early 2000s. She has pleaded not guilty and will face a Manhattan federal jury later this month.
In an unredacted motion filed Friday, the government argued that Judge Alison Nathan should forbid "the defense from making the baseless argument" that Maxwell was a victim of the late financier, who killed himself in a New York lockup weeks after his July 2019 arrest for sexually exploiting scores of underage girls.
"The Government's years-long investigation has not developed any evidence that the defendant was victimized in any way by Jeffrey Epstein," the court filing stated.
Prosecutors said that in "many" meetings with Maxwell's legal team—including before the grand jury heard the case—defense attorneys "made a variety of factual assertions in order to dissuade" the feds from charging Maxwell. Those arguments did not include allegations that Epstein abused the heiress, according to the government.
Still, the government said, Maxwell's lawyers declined to answer whether they plan to offer such evidence when the trial's opening statements begin on Nov. 29.
Maxwell's attorneys should be required "to make an offer of proof before permitting any questioning or argument alleging that [Maxwell] is a victim of abuse by Epstein—or anyone else, for that matter," prosecutors added.
Allowing this line of argument "would be highly prejudicial to the Government and confusing to the jury," the government stated. "It would primarily serve to invite the jury to feel sympathy for the defendant, providing an unlawful basis for jury nullification."
"Consent ... is not a valid defense to sex trafficking of minors."
Last week, Nathan denied prosecutors' request to keep this particular motion confidential, calling their proposed redactions "overbroad."
Assistant U.S. Attorneys had argued the court filing should remain sealed until after trial because it "would likely result in significant publicity, which would be highly prejudicial to the Government if in fact there is no good-faith basis for the argument, as the Government suspects will be the case."
The pretrial motion on admissible evidence is one of many before Judge Nathan, who will rule on what arguments, exhibits and testimony to exclude from trial.
Maxwell is requesting the court bar statements made by alleged co-conspirators and exhibits including framed photographs, a box containing a sex toy described as "Twin Torpedos," and a document titled "Household Manual."
"Ms. Maxwell did not create the document and no evidence exists suggesting that she did," her lawyers wrote of the household instructions. They added that the document "reflects a lifestyle that many jurors may find offensive."
The socialite's lawyers also want the court to toss evidence related to the indictment's Minor Victim 3, arguing she was of the age of consent in the U.K., where the alleged abuse occurred in 1994 and 1995.
Meanwhile, Maxwell is seeking to use "consent" as a defense in her case, arguing some victims could have been charged with prostitution at the time of the alleged trafficking.
"Depending on the age of the accusers during the time frame of the conspiracy, consent may be an appropriate and viable defense," Maxwell's attorneys wrote in a motion. They argued that in Florida, where Minor Victim 4 lived and was abused by Epstein, the age of consent is 18 and "at the time of the alleged offense, individuals under the age of 18 could be charged with commission of the crime of prostitution."
In connection to the charges related to Minor Victim 4, Maxwell's team said, "it is appropriate to raise the defense of consent to engage in prosecution."
"Consent is not a valid defense to any of the counts in the Indictment," the government noted in a filing of its own. "It is not a valid defense to sex trafficking of minors."
@kbriqueletkate.briquelet@thedailybeast.com
Got a tip? Send it to The Daily Beast here.


text:
This is a beta version of NNDB
Search: All Names Living people Dead people Band Names Book Titles Movie Titles Full Text for
Manages the DeYoung Museum at Golden Gate Park, and the Legion of Honor at Lincoln Park.
http://www.thinker.org/
Charles Crocker Business c. 1939 Crocker Capital
George R. Roberts Business 1944 Kohlberg Kravis Roberts
Do you know something we don't?
Submit a correction or make a comment about this profile
Copyright ©2016 Soylent Communications
NNDB MAPPER
Requires Flash 7+ and Javascript.
NNDB has added thousands of bibliographies for people, organizations, schools, and general topics, listing more than 50,000 books and 120,000 other kinds of references. They may be accessed by the "Bibliography" tab at the top of most pages, or via the "Related Topics" box in the sidebar. Please feel free to suggest books that might be critical omissions.