We study the problem of zero-delay coding for the transmission of a Markov source over a noisy channel with feedback and present a reinforcement learning solution which is guaranteed to approach optimality. To this end, we formulate the problem as a Markov decision process (MDP) where the state is a probability-measure valued predictor/belief and the actions are quantizer maps. This MDP formulation has been used to show the optimality of certain classes of encoder policies in prior work, but their computation is prohibitively complex due to the uncountable nature of the constructed state space. Based on recent results for partially observed MDPs, we present an approximation of the belief MDP using a sliding finite window of channel outputs and quantizers. Under an appropriate notion of predictor stability, we show that the lowest distortion achievable by such a sliding finite window policy approaches the true lowest distortion as the window length increases. We give sufficient conditions for predictor stability to hold. Finally, we propose a Q-learning algorithm which provably converges to the optimal policy and provide a detailed comparison of the sliding finite window scheme with another approximation scheme which quantizes the belief MDP in a nearest neighbor fashion, as well as other coding schemes from the literature.

In the classical lossy source coding problem, one encodes long blocks of source symbols that enables the distortion to approach the ultimate Shannon limit. This approach is undesirable in many delay-sensitive applications. We consider the zero-delay case, where the goal is to encode and decode a finite-alphabet Markov source without any delay. It has been shown that this problem lends itself to stochastic control techniques, which lead to existence, structural, and approximation results. However, these techniques have only resulted in computationally prohibitive algorithms for code design. We present a practical reinforcement learning design algorithm and rigorously prove its asymptotic optimality. In particular, we show that a quantized Q-learning algorithm can be used to obtain a near-optimal coding policy for this problem. The proof builds on recent results on quantized Q-Iearning for weak Feller controlled Markov chains whose application necessitates the development of supporting technical results on regularity and stability properties, and relating the solutions for discounted and average cost criteria problems. These theoretical results are supported by simulations.

In multi-agent reinforcement learning (MARL) and game theory, agents repeatedly interact and revise their strategies as new data arrives, producing a sequence of strategy profiles. This paper studies sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning, where an agent who is best responding in one period does not switch its strategy in the next period. This constraint merely requires that optimizing agents do not switch strategies, but does not constrain the non-optimizing agents in any way, and thus allows for exploration. Sequences with this property are called satisficing paths, and arise naturally in many MARL algorithms. A fundamental question about strategic dynamics is such: for a given game and initial strategy profile, is it always possible to construct a satisficing path that terminates at an equilibrium? The resolution of this question has implications about the capabilities or limitations of a class of MARL algorithms. We answer this question in the affirmative for normal-form games. Our analysis reveals a counterintuitive insight that suboptimal, and perhaps even reward deteriorating, strategic updates are key to driving play to equilibrium along a satisficing path.

Independent learners are agents that employ single-agent algorithms in multi-agent systems, intentionally ignoring the effect of other strategic agents. This paper studies mean-field games from a decentralized learning perspective with two aims: (i) to identify structure that can guide algorithm design, and (ii) to understand emergent behaviour in systems of independent learners. We study a new model of partially observed mean-field games with finitely many players, local action observability, and partial observations of the global state. Specific observation channels considered include (a) global observability, (b) mean-field observability, (c) compressed mean-field observability, and (d) only local observability. We establish conditions under which the control problem of a given agent is equivalent to a fully observed MDP, as well as conditions under which the control problem is equivalent only to a POMDP. Using the connection to MDPs, we prove the existence of perfect equilibrium among memoryless stationary policies under mean-field observability. Using the connection to POMDPs, we prove convergence of learning iterates obtained by independent learners under any of our observation channels. We interpret the limiting values as subjective value functions, which an agent believes to be relevant to its control problem. These subjective value functions are used to propose subjective Q-equilibrium, a new solution concept whose existence is proved under mean-field or global observability. Furthermore, we provide a decentralized independent learning algorithm, and by adapting the recently developed theory of satisficing paths to allow for subjectivity, we prove that it drives play to subjective Q-equilibrium. Our algorithm is decentralized, in that it uses only local information for learning and allows players to use different, heterogeneous policies during play. As such, it departs from the conventional representative agent approach common to other algorithms for mean-field games.

In the classical lossy source coding problem, one encodes long blocks of source symbols that enables the distortion to approach the ultimate Shannon limit. Such a block-coding approach introduces large delays, which is undesirable in many delay-sensitive applications. We consider the zero-delay case, where the goal is to encode and decode a finite-alphabet Markov source without any delay. It has been shown that this problem lends itself to stochastic control techniques, which lead to existence, structural, and general structural approximation results. However, these techniques so far have only resulted in computationally prohibitive algorithmic implementations for code design. To address this problem, we present a practically implementable reinforcement learning design algorithm and rigorously prove its asymptotic optimality. In particular, we show that a quantized Q-learning algorithm can be used to obtain a near-optimal coding policy for this problem. The proof builds on recent results on quantized Q-learning for weakly Feller controlled Markov chains whose application necessitates the development of supporting technical results on regularity and stability properties, and relating the optimal solutions for discounted and average cost infinite horizon criteria problems. These theoretical results are supported by simulations.

We introduce a framework and optimal ‘fresh’ caching for a content distribution network (CDN) comprising a front-end local cache and a back-end database. The data content is dynamically updated at a back-end database and end-users are interested in the most-recent version of that content. We formulate the average cost minimization problem that captures the system’s cost due to the service of aging content as well as the regular cache update cost. We consider the cost minimization problem from two individual perspectives based on the available information to either side of the CDN: the back-end database perspective and the front-end local cache perspective. For the back-end database, the instantaneous version of content is observable but the exact demand is not. Caching decisions made by the back-end database are termed ‘push-based caching.’ For the front-end local cache, the age of content version in the cache is not observable, yet the instantaneous demand is. Caching decisions made by the front-end local cache are termed ‘pull-based caching.’ Our investigations reveal which type of information, updates, or demand dynamic, is of higher value towards achieving the minimum cost based on other network parameters including content popularity, update rate, and demand intensity.

Reinforcement learning algorithms often require finiteness of state and action spaces in Markov decision processes (MDPs) (also called controlled Markov chains) and various efforts have been made in the literature towards the applicability of such algorithms for continuous state and action spaces. In this paper, we show that under very mild regularity conditions (in particular, involving only weak continuity of the transition kernel of an MDP), Q-learning for standard Borel MDPs via quantization of states and actions (called Quantized Q-Learning) converges to a limit, and furthermore this limit satisfies an optimality equation which leads to near optimality with either explicit performance bounds or which are guaranteed to be asymptotically optimal. Our approach builds on (i) viewing quantization as a measurement kernel and thus a quantized MDP as a partially observed Markov decision process (POMDP), (ii) utilizing near optimality and convergence results of Q-learning for POMDPs, and (iii) finally, near-optimality of finite state model approximations for MDPs with weakly continuous kernels which we show to correspond to the fixed point of the constructed POMDP. Thus, our paper presents a very general convergence and approximation result for the applicability of Q-learning for continuous MDPs.

It is known that under fixed-rate information constraints, adaptive quantizers can be used to stabilize an open-loop-unstable linear system on$\mathbb {R}^{n}$driven by unbounded noise. These adaptive schemes can be designed so that they have near-optimal rate, and the resulting system will be stable in the sense of having an invariant probability measure, or ergodicity, as well as boundedness of the state second moment. Although structural results and information theoretic bounds of encoders have been studied, the performance of such adaptive fixed-rate quantizers beyond stabilization has not been addressed. In this paper, we propose a two-part adaptive (fixed-rate) coding scheme that achieves state second moment convergence to the classical optimum (i.e., for the fully observed setting) under mild moment conditions on the noise process. The first part, as in prior work, leads to ergodicity (via positive Harris recurrence) and the second part ensures that the state second moment converges to the classical optimum at high rates. These results are established using an intricate analysis which uses random-time state-dependent Lyapunov stochastic drift criteria as a core tool.

It is known that fixed rate adaptive quantizers can be used to stabilize an open-loop-unstable linear system driven by unbounded noise. These quantizers can be designed so that they have near-optimal rate, and the resulting system will be stable in the sense of having an invariant probability measure, or ergodicity, as well as the boundedness of the state second moment. However, results on the minimization of the state second moment for such quantizers, an important goal in practice, do not seem to be available. In this paper, we construct a two-part adaptive coding scheme that is asymptotically optimal in terms of the second moments as the data rate grows large. The first part, as in prior work, leads to ergodicity (via positive Harris recurrence) and the second part attains order optimality of the invariant second moment, resulting in near optimal performance at high rates.

In the theory of Partially Observed Markov Decision Processes (POMDPs), existence of optimal policies have in general been established via converting the original partially observed stochastic control problem to a fully observed one on the belief space, leading to a belief-MDP. However, computing an optimal policy for this fully observed model, and so for the original POMDP, using classical dynamic or linear programming methods is challenging even if the original system has finite state and action spaces, since the state space of the fully observed belief-MDP model is always uncountable. Furthermore, there exist very few rigorous value function approximation and optimal policy approximation results, as regularity conditions needed often require a tedious study involving the spaces of probability measures leading to properties such as Feller continuity. In this paper, we study a planning problem for POMDPs where the system dynamics and measurement channel model are assumed to be known. We construct an approximate belief model by discretizing the belief space using only finite window information variables. We then find optimal policies for the approximate model and we rigorously establish near optimality of the constructed finite window control policies in POMDPs under mild non-linear filter stability conditions and the assumption that the measurement and action sets are finite (and the state space is real vector valued). We also establish a rate of convergence result which relates the finite window memory size and the approximation error bound, where the rate of convergence is exponential under explicit and testable exponential filter stability conditions. While there exist many experimental results and few rigorous asymptotic convergence results, an explicit rate of convergence result is new in the literature, to our knowledge.

Optimal zero-delay coding (quantization) of$\mathbb {R}^{d}$-valued linearly generated Markov sources is studied under quadratic distortion. The structure and existence of deterministic and stationary coding policies that are optimal for the infinite horizon average cost (distortion) problem are established. Prior results studying the optimality of zero-delay codes for Markov sources for infinite horizons either considered finite alphabet sources or, for the$\mathbb {R}^{d}$-valued case, only showed the existence of deterministic and non-stationary Markov coding policies or those which are randomized. In addition to existence results, for finite blocklength (horizon)$T$the performance of an optimal coding policy is shown to approach the infinite time horizon optimum at a rate$O\left({\frac {1}{T}}\right)$. This gives an explicit rate of convergence that quantifies the near-optimality of finite window (finite-memory) codes among all optimal zero-delay codes.

We investigate a privacy-signaling game problem in which a sender with privacy concerns observes a pair of correlated random vectors which are modeled as jointly Gaussian. The sender aims to hide one of these random vectors and convey the other one whereas the objective of the receiver is to accurately estimate both of the random vectors. We analyze these conflicting objectives in a game theoretic framework with quadratic costs where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg (Bayesian persuasion) equilibria. We show that a payoff dominant Nash equilibrium among all admissible policies is attained by a set of explicitly characterized linear policies. We also show that a payoff dominant Nash equilibrium coincides with a Stackelberg equilibrium. We formulate the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the random variables is observed at the sender. We show that this MMSE Gaussian Information Bottleneck Problem admits a linear solution which is explicitly characterized in the paper. We provide explicit conditions on when the optimal solutions, or equilibrium solutions in the Nash setup, are informative or noninformative.

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions.

Signaling game problems investigate communication scenarios where encoder(s) and decoder(s) have misaligned objectives due to the fact that they either employ different cost functions or have inconsistent priors. We investigate a signaling game problem where an encoder observes a multi-dimensional source and conveys a message to a decoder, and the quadratic objectives of the encoder and decoder are misaligned due to a bias vector. For the scalar case, Crawford and Sobel in their seminal paper, show that under certain technical assumptions an encoding policy must be a quantization policy at any Nash equilibrium. We first provide a set of geometry conditions that needs to be satisfied in equilibrium considering any multi-dimensional source. Then, we consider multi-dimensional sources with independent and identically distributed components and completely characterize conditions under which a Nash equilibrium with a linear encoder exists. In particular, we show that if the components of the bias vector are not equal in magnitude, then there exists a linear equilibrium if and only if the source distribution is Gaussian. On the other hand, for a linear equilibrium to exist in the case of equal bias components, it is required that the source density is symmetric around its mean. Moreover, in the case of Gaussian sources, our results have a rate-distortion theoretic implication that achievable rates and distortions in the considered game theoretic setup can be obtained from their team theoretic counterpart.

In statistical decision theory involving a single decision-maker, one says that an information structure is better than another one if for any cost function involving a hidden state variable and an action variable which is restricted to be only a function of some measurement, the solution value under the former is not worse than the value under the latter. For finite probability spaces, Blackwell's celebrated theorem on comparison of information structures leads to a complete characterization on when one information structure is better than another. For stochastic games with incomplete information, due to the presence of competition among decision makers, in general such an ordering is not possible since additional information can lead to equilibria perturbations with positive or negative values to a player. However, for zero-sum games in a finite probability space, Peski introduced a complete characterization of ordering of information structures. In this paper, we obtain an infinite dimensional (standard Borel) generalization of Peski's result. A corollary of our analysis is that more information cannot hurt a decision maker taking part in a zero-sum game in standard Borel spaces. During our analysis, we establish two novel supporting results: (i) a refined existence result for equilibria in zero-sum games with incomplete information when compared with the prior literature and ii) a partial converse to Blackwell's ordering of information structures in the standard Borel space setup.

We consider a privacy-signaling game problem in which a transmitter with privacy concerns and a receiver, which does not pay attention to these privacy concerns, communicate. In this communication scenario, the transmitter observes a pair of correlated random variables which are modeled as jointly Gaussian. The transmitter constructs its message based on these random variables with the aim to hide one of them and convey the other one. In contrast, the objective of the receiver is to accurately estimate both of the random variables so as to gather as much information as possible. These conflicting objectives are analyzed in a game theoretic framework where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg equilibria. We show that a payoff dominant (i.e., most desirable for both players) Nash equilibrium is attained by affine policies and we explicitly characterize these policies. In addition, the strategies at the characterized Nash equilibrium is shown to form also a Stackelberg equilibrium. Furthermore, we show that there always exists an informative Stackelberg equilibrium for the multidimensional parameter setup. We also revisit the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the sender. We fully characterize the Stackelberg equilibria under certain conditions and when these conditions are not met we establish the existence of informative equilibria.

We investigate the equilibrium behavior for the decentralized quadratic cheap talk problem in which an encoder and a decoder, viewed as two decision makers, have misaligned objective functions. In prior work, we have shown that the number of bins under any equilibrium has to be at most countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we refine this result in the context of exponential and Gaussian sources. For exponential sources, a relation between the upper bound on the number of bins and the misalignment in the objective functions is derived, the equilibrium costs are compared, and it is shown that there also exist equilibria with infinitely many bins under certain parametric assumptions. For Gaussian sources, it is shown that there exist equilibria with infinitely many bins.

We study the following problem: Given a stochastic nonlinear system controlled over a possibly noisy communication channel, what is the largest class of such channels for which there exist coding and control policies so that the closed-loop system is stochastically stable? The stability criterion considered is asymptotic mean stationarity (AMS). We first develop a general method (based on ergodic theory) to derive fundamental lower bounds on the channel capacity necessary for achieving asymptotic mean stationarity. These bounds are consistent, and more refined in comparison, with the bounds obtained earlier via information-theoretic methods. Moreover, our approach is more versatile in view of the models considered and allows for finer lower bounds when the AMS measure is known to admit further properties such as moment constraints.

We consider the problem of zero-delay coding of a dynamical system over a discrete noiseless channel under three estimation criteria concerned with the low-distortion regime. For these three criteria, formulated stochastically in terms of a probability distribution for the initial state, we characterize the smallest channel capacities above which the estimation objectives can be achieved. The results establish further connections between topological and metric entropies of dynamical systems and information theory.

This paper studies state estimation over noisy channels for stochastic non-linear systems. We consider three estimation objectives, a strong and a weak form of almost sure stability of the estimation error as well as quadratic stability in expectation. For all three objectives, we derive lower bounds on the smallest channel capacity Coabove which the objective can be achieved with an arbitrarily small error. Lower bounds are obtained via a dynamical systems (through a novel construction of a dynamical system), an information-theoretic and a random dynamical systems approach. The first two approaches show that for a large class of systems, such as additive noise systems, Co = ∞, i.e., the estimation objectives cannot be achieved via channels of finite capacity. The random dynamical systems approach is shown to be operationally non-adequate for the problem, since it yields finite lower bounds Co under mild assumptions. Finally, we prove that a memoryless noisy channel in general constitutes no obstruction to asymptotic almost sure state estimation with arbitrarily small errors, when there is no noise in the system.

In many applications, the common assumption that a driving noise process affecting a system is independent or Markovian may not be realistic, but the noise process may be assumed to be stationary. To study such problems, this paper investigates stochastic stability properties of a class of non-Markovian processes, where the existence of a stationary measure, asymptotic mean stationarity and ergodicity conditions are studied. Applications in adaptive quantization and stochastic networked control are presented.

The optimal zero delay coding of a finite-state Markov source is considered. The existence and structure of optimal codes are studied using a stochastic control formulation. Prior results in the literature established the optimality of deterministic Markov (Walrand–Varaiya-type) coding policies for the finite time horizon problem, and the optimality of both deterministic nonstationary and randomized stationary policies for the infinite time horizon problem. Our main result here shows that for any irreducible and aperiodic Markov source with a finite alphabet,deterministic and stationaryMarkov coding policies are optimal for the infinite horizon problem. In addition, the finite block length (time horizon) performance of an optimal (stationary and Markov) coding policy is shown to approach the infinite time horizon optimum at a rate$O(1/T)$. The results are extended to systems, where zero delay communication takes place across a noisy channel with noiseless feedback.

This paper studies continuity properties of single and multi stage estimation and stochastic control problems with respect to initial probability distributions and applications of these results to the study of robustness of control policies applied to systems with incomplete probabilistic models. We establish that continuity and robustness cannot be guaranteed under weak and setwise convergences, but the optimal cost is continuous under the more stringent topology of total variation for stage-wise cost functions that are nonnegative, measurable, and bounded. Under further conditions on either the measurement channels or the source processes, however, weak convergence is sufficient. We also discuss similar properties under the Wasserstein distance. These results are shown to have direct implications, positive or negative, for robust control: If an optimal control policy is applied to a prior model P̃, and if P̃ is close to the true model P, then the application of the incorrect optimal policy to the true model leads to a loss that is continuous in the distance between P̃ and P under total variation, and under some setups, weak convergence distance measures.

In this study, dynamic and repeated quadratic cheap talk and signaling game problems are investigated. These involve encoder and decoders with mismatched performance objectives, where the encoder has a bias term in the quadratic cost functional. We consider both Nash equilibria and Stackelberg equilibria as our solution concepts, under a perfect Bayesian formulation. These two lead to drastically different characteristics for the equilibria. For the cheap talk problem under Nash equilibria, we show that fully revealing equilibria cannot exist and the final state equilibria have to be quantized for a large class of source models; whereas, for the Stackelberg case, the equilibria must be fully revealing regardless of the source model. In the dynamic signaling game where the transmission of a Gaussian source over a Gaussian channel is considered, the equilibrium policies are always linear for scalar sources under Stackelberg equilibria, and affine policies constitute an invariant subspace under best response maps for Nash equilibria.

This paper is concerned with the following problem: Given a stochastic non-linear system controlled over a noisy channel, what is the largest class of channels for which there exist coding and control policies so that the closed loop system is stochastically stable? Stochastic stability notions considered are stationarity, ergodicity or asymptotic mean stationarity. We do not restrict the state space to be compact, for example systems considered can be driven by unbounded noise. Necessary and sufficient conditions are obtained for a large class of systems and channels. A generalization of Bode's Integral Formula for a large class of non-linear systems and information channels is obtained.

Optimal zero-delay coding (quantization) of a finite-state Markov source is considered. Building on our earlier work and previous literature, using a stochastic control problem formulation, the existence and structure of optimal quantization policies are studied. Our main result establishes, for infinite horizon problems, the optimality of deterministic and stationary (Walrand-Varaiya type) Markov coding policies. In addition, the ε-optimality of finite-memory quantizers is established and the dependence between the memory length and ε is quantified. Numerical results are also presented.

This paper studies fixed-rate randomized vector quantization under the constraint that the quantizer's output has a given fixed probability distribution. A general representation of randomized quantizers that includes the common models in the literature is introduced via appropriate mixtures of joint probability measures on the product of the source and reproduction alphabets. Using this representation and results from optimal transport theory, the existence of an optimal (minimum distortion) randomized quantizer having a given output distribution is shown under various conditions. For sources with densities and the mean square distortion measure, it is shown that this optimum can be attained by randomizing quantizers having convex codecells. For stationary and memoryless source and output distributions, a rate-distortion theorem is proved, providing a single-letter expression for the optimum distortion in the limit of large blocklengths.

This paper studies a Shannon-theoretic version of the generalized distribution preserving quantization problem where a stationary and memoryless source is encoded subject to a distortion constraint and the additional requirement that the reproduction also be stationary and memoryless with a given distribution. The encoder and decoder are stochastic and assumed to have access to independent common randomness. Recent work has characterized the minimum achievable coding rate at a given distortion level when unlimited common randomness is available. Here, we consider the general case where the available common randomness may be rate limited. Our main result completely characterizes the set of achievable coding and common randomness rate pairs at any distortion level, thereby providing the optimal tradeoff between these two rate quantities. We also consider two variations of this problem where we investigate the effect of relaxing the strict output distribution constraint and the role of private randomness used by the decoder on the rate region. Our results have strong connections with Cuff's recent work on distributed channel synthesis. In particular, our achievability proof combines a coupling argument with the approach developed by Cuff, where instead of explicitly constructing the encoder-decoder pair, a joint distribution is constructed from which a desired encoder-decoder pair is established. We show, however, that for our problem, the separated solution of first finding an optimal channel and then synthesizing this channel results in a suboptimal rate region.

Optimal zero-delay coding (quantization) of a vector-valued Markov source driven by a noise process is considered. Using a stochastic control problem formulation, the existence and structure of optimal quantization policies are studied. For a finite-horizon problem with bounded per-stage distortion measure, the existence of an optimal zero-delay quantization policy is shown provided that the quantizers allowed are ones with convex codecells. The bounded distortion assumption is relaxed to cover cases that include the linear quadratic Gaussian problem. For the infinite horizon problem and a stationary Markov source, the optimality of deterministic Markov coding policies is shown. The existence of optimal stationary Markov quantization policies is also shown provided randomization that is shared by the encoder and the decoder is allowed.

We consider the transmission of a Gaussian vector source over a multidimensional Gaussian channel where a random or a fixed subset of the channel outputs are erased. Within the setup where the only encoding operation allowed is a linear unitary transformation on the source, we investigate the minimum mean-square error (MMSE) performance, both in average, and also in terms of guarantees that hold with high probability as a function of the system parameters. Under the performance criterion of average MMSE, necessary conditions that should be satisfied by the optimal unitary encoders are established and explicit solutions for a class of settings are presented. For random sampling of signals that have a low number of degrees of freedom, we present MMSE bounds that hold with high probability. Our results illustrate how the spread of the eigenvalue distribution and the unitary transformation contribute to these performance guarantees. The performance of the discrete Fourier transform (DFT) is also investigated. As a benchmark, we investigate the equidistant sampling of circularly wide-sense stationary signals, and present the explicit error expression that quantifies the effects of the sampling rate and the eigenvalue distribution of the covariance matrix of the signal. These findings may be useful in understanding the geometric dependence of signal uncertainty in a stochastic process. In particular, unlike information theoretic measures such as entropy, we highlight the basis dependence of uncertainty in a signal with another perspective. The unitary encoding space restriction exhibits the most and least favorable signal bases for estimation.

We consider the problem of optimal randomized vector quantization under a constraint on the output's distribution. The problem is formalized by introducing a general representation of randomized quantization via probability measures over the space of joint distributions on the source and reproduction alphabets. Using this representation and results from optimal transport theory, we show the existence of an optimal (minimum distortion) randomized quantizer having a fixed output distribution under various conditions. For sources with densities and the mean square distortion measure, we show that this optimum can be attained by randomizing quantizers having convex code cells. We also consider a relaxed version of the problem where the output marginal must belong to some neighborhood (in the weak topology) of a fixed probability measure. We demonstrate that finitely randomized quantizers form an optimal class for the relaxed problem.

The problem of reliable communication over the memoryless state-dependent multiple-access channel (MAC) is considered, where the encoders and the decoder are provided with various degrees of asymmetric noisy channel state information (CSI). For the case where the encoders observe causal, asymmetric noisy CSI and the decoder observes complete CSI, inner and outer bounds to the capacity region, which are tight for the sum-rate capacity, are provided. Next, single-letter characterizations for the channel capacity regions under each of the following system settings are established: 1) the CSI at the encoders are asymmetric deterministic functions of the CSI at the decoder and the encoders have noncausal noisy CSI; 2) the encoders observe asymmetric noisy CSI with asymmetric delays and the decoder observes complete CSI; 3) a degraded message set scenario with asymmetric noisy CSI at the encoders and complete and/or noisy CSI at the decoder. The main component in these results is a generalization of a recently introduced converse coding approach for the MAC with asymmetric quantized CSI at the encoders and herein considerably extended and adapted for the noisy CSI setup.

The optimal causal (zero-delay) coding of a partially observed Markov process is studied, where the cost to be minimized is a bounded, nonnegative, additive, measurable single-letter function of the source and the receiver output. A structural result is obtained extending Witsenhausen's and Walrand-Varaiya's structural results on optimal causal coders to more general state spaces and to a partially observed setting. The decentralized (multiterminal) setup is also considered. For the case where the source is an i.i.d. process, it is shown that an optimal solution to the decentralized causal coding of correlated observations problem is memoryless. For Markov sources, a counterexample to a natural separation conjecture is presented.

We consider the problem of reliable communication over multiple-access channels (MAC) where the channel is driven by an independent and identically distributed state process and the encoders and the decoder are provided with various degrees of asymmetric (noisy or partial) channel state information (CSI). Namely, we provide a single letter characterization for the capacity region when the encoders have access to non-causal asymmetric partial CSI and the decoder has complete CSI. When the encoders observe asymmetric noisy CSI with asymmetric delays and the decoder observes complete CSI, we provide a single letter characterization for the capacity region. Finally, we consider a cooperative scenario with common and private messages, with noisy CSIT and complete CSIR and provide a single letter expression for the capacity region. For the cooperative scenario, we also note that as soon as the common message encoder does not have access to CSI, then for any noisy CSIT and CSIR setup it is possible to obtain a single letter characterization for the capacity region.

Stabilization of nonstationary linear systems over noisy communication channels is considered. Stochastically stable sources, and unstable but noise-free or bounded-noise systems have been extensively studied in the information theory and control theory literature since the 1970s, with a renewed interest in the past decade. There have also been studies on noncausal and causal coding of unstable/nonstationary linear Gaussian sources. In this paper, tight necessary and sufficient conditions for stochastic stabilizability of unstable (nonstationary) possibly multidimensional linear systems driven by Gaussian noise over discrete channels (possibly with memory and feedback) are presented. Stochastic stability notions include recurrence, asymptotic mean stationarity and sample path ergodicity, and the existence of finite second moments. Our constructive proof uses random-time state-dependent stochastic drift criteria for stabilization of Markov chains. For asymptotic mean stationarity (and thus sample path ergodicity), it is sufficient that the capacity of a channel is (strictly) greater than the sum of the logarithms of the unstable pole magnitudes for memoryless channels and a class of channels with memory. This condition is also necessary under a mild technical condition. Sufficient conditions for the existence of finite average second moments for such systems driven by unbounded noise are provided.

A single-letter characterization is provided for the capacity region of finite-state multiple-access channels, when the channel state process is an independent and identically distributed sequence, the transmitters have access to partial (quantized) state information, and complete channel state information is available at the receiver. The partial channel state information is assumed to be asymmetric at the encoders. As a main contribution, a tight converse coding theorem is presented. The difficulties associated with the case when the channel state has memory are discussed and connections to decentralized stochastic control theory are presented.

We consider the feedback capacity of a class of symmetric finite-state Markov channels. Here, symmetry (termed “quasi-symmetry”) is defined as a generalized version of the symmetry defined for discrete memoryless channels. The symmetry yields the existence of a hidden Markov noise process that depends on the channel's state process and facilitates the channel description as a function of input and noise, where the function satisfies a desirable invertibility property. We show that feedback does not increase capacity for such class of finite-state channels and that both their nonfeedback and feedback capacities are achieved by an independent and uniformly distributed (i.u.d.) input. As a result, the channel capacity is explicitly given as a difference of output and noise entropy rates, where the output is driven by the i.u.d. input.

The optimal real-time coding of a partially observed Markov process is studied, where the cost to be minimized is an arbitrary non-negative, additive, single-letter function of the source and the decoder output. Both centralized and decentralized settings are considered. A structural result is obtained extending Witsenhausen's structural results on the optimal realtime coders to a partially observed setting. The decentralized-control concept of signaling (the action that decision makers communicate via their actions) is interpreted in a real-time decentralized coding setting. When signaling is present, a counterexample to a natural separation conjecture is presented.

A stochastic stability result for a class of adaptive quantizers which were introduced by Goodman and Gersho is presented. We consider a case where the input process is a linear Markov source which is not necessarily stable. We present a stochastic stability result for the estimation error and the quantizer, thus generalizing the stability result of Goodman and Gersho to a Markovian, and furthermore to an unstable, setting. Furthermore, it is shown that, there exists a unique invariant distribution for the state and the quantizer parameters under mild irreducibility conditions. The second moment under the invariant distribution is finite, if the system noise is Gaussian.

We provide a single letter characterization of the capacity region for independent, identically distributed, finite-state channels, with partial (quantized) state information, when the channel state information is available at the receiver. The partial state information is asymmetric at the encoders. The problem is practically relevant, and provides a tractable optimization problem. We also consider the case where the channel has memory.

The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashev's classic result is extended to finite-state ergodic Markov channels. For these channels, a single-letter characterization of the reliability function is presented, under the assumption of full causal output feedback, and full causal observation of the channel state both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference (ISI). Specifically, the convex-analytic approach to Markov decision processes is adopted in order to handle problems with stopping time horizons induced by variable-length coding schemes.

We consider the reliability function of Markov channels with feedback and variable length channel codes. We extend Burnashev's [M.V. Burnashev, 1976] classic result to this case and present a single letter characterization for the reliability function.

We study the capacity of Markov channels with causal deterministic partial (quantized) state feedback. We assume the feedback channel to be memoryless, the channel state process to be Markovian, belong to a finite set, and the state and observation transitions to satisfy some general mixing conditions. For such channels, we obtain a single-letter characterization for the capacity with feedback. We further show that for every e > 0, there exists a finite length memory (sliding) encoder structure that leads to an epsiv-optimal capacity; hence practically optimal performance can be achieved. We show that the non-linear filter generating the conditional state density provides the sufficient statistic for the optimal coding scheme.