A dynamic program to achieve capacity of multiple access channel with noiseless feedback

Finding the capacity and capacity achieving scheme of Multiple Access Channel with noiseless feedback (MAC-NF) is a fundamental problem in communication that has been studied from the lens of information theory [3]. It was shown by Gaarder and Wolf [4] that feedback strictly increases the capacity of this channel. Later Cover and Leung [5] provided an achievable rate region for this channel using block Markov coding and showed it to be tight for a class of channels for which each encoder can perfectly decode the transmitted symbol of the other using feedback and its own transmitted symbol (henceforth referred to as Cover-Leung Channels). Kramer [1] provided a multi-letter directed information expression for the capacity of this channel. For Gaussian MAC with feedback, Ozarow [6] provided a linear scheme that achieves capacity and shows that for this channel, the expression for capacity is single letter. Since then finding a single letter expression for MAC channel with feedback has been an open problem.

Recently, Anastasopoulos and Pradhan in [2] presented a connection between the problem of Decentralized sequential active hypothesis testing (DSAHT) and that of finding capacity of a multiple access channel with noiseless feedback. DSAHT problem consists of minimizing the terminal probability of error for MAC-NF. For this, the authors show that this can be posed as a decentralized stochastic control problem, and using common information approach [7], they pose it as a dynamic program for common agent and show that there exists Markovian strategies that are optimal, where these policies are Markovian with respect to a common belief state $\pi_{t}$ that puts a belief on private messages of the users. For the problem of achieving capacity, they show that the multi letter expression of capacity defined by Kramer [1] is a dynamic optimization problem. However, the instantaneous costs involve private beliefs of the senders on their own transmitted symbols, that are not observed by each other. Thus, the instantaneous costs can not be written as a function of a state that is observed by all the players, in effect showing that there is no notion of state and this problem can not decomposed sequentially through as a dynamic program. However, they argue that one can still restrict oneself to Markovian policies that are optimal for DSAHT problem to solve for the dynamic optimization problem which in turn would solve for finding capacity. In summary, their main result shows that there exist a common belief based Markovian strategy that achieves capacity for this channel, and thus one can restrict oneself to this class of strategies to evaluate capacity. This is given by solving a dynamic optimization problem that can not be sequentially decomposed (i.e. does not have a dynamic program).

In this paper, we build upon their work to show that there indeed exists a state and therefore a dynamic program that decomposes this optimization problem, and thus there exists a Bellman fixed-point equation to evaluate capacity of this channel. We do this by again using the common agent approach [7] and constructing a new common belief state $\tilde{\pi}_{t}$ that puts a measure on the private messages of the users as well as their private beliefs, that appear in the instantaneous cost to achieve capacity, as described above. Based on this new common belief state, we show that this is indeed a state of the system such that it is a controlled Markov process for the problem where the instantaneous cost can written as a function of this state and user’s partial functions that map their private state to their transmitted symbols. This shows that one can in principle solve for capacity expression, and the capacity achieving policy, by solving a parameterized Bellman type fixed-point dynamic programming (DP) equation with state as $\tilde{\pi}_{t}$. We further show that this DP equation can be further simplified to a DP with state as common belief on just the messages of the transmitters i.e. $\pi_{t}$, the same state considered in [2] for the DSAHT problem. This provides a single letter characterization of the capacity of this channel.

The paper is structured as follows. Section II provides the model. In Section III, we discuss previous results. In Section IV we present our main result. In Section V, we present conclusion and future work.

We consider a two-user discrete memoryless Multiple Access Channel with Noiseless Feedback (MAC-NF). The input symbols $X^{1}$, $X^{2}$ and the output symbol $Y$ take values in the finite alphabets $\mathcal{X}^{1}$, $\mathcal{X}^{2}$ and $\mathcal{Y}$, respectively.¹¹1We use discrete alphabets to simplify exposition and avoid measure theoretic technicalities that could arise from the continuous alphabets. However, our results go through for continuous alphabets under appropriate technical regularity assumptions. The channel is memoryless in the sense that the current channel output is independent of all the past channel inputs and the channel outputs, i.e.,

Our model considers noiseless feedback with unit delay, that is, at time $t$, the presence of the channel outputs $y_{1:t-1}$ to both encoders.

Consider the problem of transmission of messages $m^{i}\in\mathcal{M}^{i}=\{1,\ldots,\mathbb{M}^{i}\},\;i=1,2$, over the MAC-NF using fixed length codes of length $n$. Encoders generate their channel inputs based on their private messages and past outputs. Thus

The decoder estimates the messages $M^{1}$ and $M^{2}$ based on $n$ channel outputs, $Y_{1:n}$ as

A fixed-length transmission scheme for the channel $Q$ is the pair $s=(f,g)$, consisting of the encoding functions $f=(f^{1},f^{2})$ with $f^{i}=f^{i}_{1:n}$ and decoding function $g$. The error probability associated with the transmission scheme $s$ is defined as

In this section, we show that there indeed exists a state and consequently a dynamic program for the capacity achieving problem. For any policy $\phi$ of the transmitters, we define a new common belief

Note that $\pi_{t}$ which is a common belief on $m$ (as defined in the previous section) can be derived from $\tilde{\pi}_{t}$ as a marginal. As discussed in the previous section, it was shown in [2] that there exists capacity achieving policy of the transmitters that is also optimal for DSAHT and is thus of the kind $x_{t}^{i}=\theta^{i}[\pi_{t-1}](m^{i})=f^{i}_{t}(\pi_{t-1},m^{i})$. Thus, we will also restrict ourselves to class of such policies which depend on private information of the player $i$ only through $m^{i}$. In other words, we do not consider policies that depend on player $i$’s complete private information in this set up which is $(\hat{\pi}^{i}_{t},m^{i})$, but only on part of it which is $m^{i}$, as considered in the previous section. In the following lemma, we show that $\tilde{\pi}_{t-1}$ can be updated using Bayes’ rule

The next step in the development is to derive simplified expressions for the mutual information quantities that are involved in the $I_{n}(\underline{\lambda})$ in (9). Specifically, we will derive simplified expressions for the quantities $I(X^{1}_{t};Y_{t}|X^{2}_{1:t},Y_{1:t-1})$, $I(X^{2}_{t};Y_{t}|X^{1}_{1:t},Y_{1:t-1})$, and $I(X^{1}_{t},X^{2}_{t};Y_{t}|Y_{1:t-1})$, or equivalently, for the quantities $H(Y_{t}|X^{2}_{1:t},Y_{1:t-1})$, $H(Y_{t}|X^{1}_{1:t},Y_{1:t-1})$, $H(Y_{t}|Y_{1:t-1})$ and $H(Y_{t}|X^{1}_{t},X^{2}_{t})$. Our results are summarized in the following theorem.

Based on Lemma 2 we can now solve for the capacity of DM-MAC-NF as a dynamic program for the common agent as follows.

The above result implies that there exist optimal Markovian policy of the transmitter $i$ that is a function of the state $\tilde{\pi}_{t}$ and $m^{i}$.