Search

In this article, we investigate partially observed Markov decision processes (POMDPs) with cost functions regularized by entropy terms describing state, observation, and control uncertainty. Standard POMDP techniques are shown to offer bounded-error solutions to these entropy-regularized POMDPs, with exact solutions possible when the regularization involves the joint entropy of the state, observation, and control trajectories. Our joint-entropy result is particularly surprising since it constitutes a novel, tractable formulation of active state estimation.

This article addresses the problem of distributed state estimation via multiple access channels (MACs). We consider a scenario where two encoders are simultaneously communicating their measurements through a noisy channel. First, the zero-error capacity region of the general $M$-input, single-output MAC is characterized using tools from nonstochastic information theory. Next, we show that a tight condition to be able to achieve uniformly bounded state estimation errors can be given in terms of the channel zero-error capacity region. This criterion relates the channel properties to the plant dynamics. These results pave the way toward understanding information flows in networked control systems with multiple transmitters.

In this article, we study the problem of controlling a partially observed Markov decision process (POMDP) to either aid or hinder the estimation of its state trajectory. We encode the estimation objectives via the smoother entropy, which is the conditional entropy of the state trajectory given measurements and controls. Consideration of the smoother entropy contrasts with previous approaches that instead resort to marginal (or instantaneous) state entropies due to tractability concerns. By establishing novel expressions for the smoother entropy in terms of the POMDP belief state, we show that both the problems of minimizing and maximizing the smoother entropy in POMDPs can surprisingly be reformulated as belief-state Markov decision processes with concave cost and value functions. The significance of these reformulations is that they render the smoother entropy a tractable optimization objective, with structural properties amenable to the use of standard POMDP solution techniques for both active estimation and obfuscation. Simulations illustrate that optimization of the smoother entropy leads to superior trajectory estimation and obfuscation compared to alternative approaches.

Recent empirical success has led to a rise in popularity of the options framework for Hierarchical Reinforcement Learning (HRL). This framework tackles the scalability problem in Reinforcement Learning (RL) by introducing a layer of abstraction (i.e. high-level options) over the (low-level) decision process. Hierarchical Imitation Learning (HIL) is the problem of learning low-level and high-level policies within HRL from expert demonstrations consisting only of the low-level actions and states, with the high-level options being hidden (or latent). Due to the latent options, recent work on HIL has focused on the development of Expectation-Maximization (EM) algorithms inspired by approaches such as the celebrated Baum-Welch algorithm for hidden Markov models (HMMs). In this work, we take a different approach and derive a new HIL framework inspired by the spectral method of moments for HMMs. The method of moments offers global and consistent convergence under mild regulatory conditions, whilst only requiring one sweep through the data set of state and action pairs, giving it a competitive run time.

We investigate state estimation of linear systems over channels having a finite state not known by the transmitter or receiver. We show that similar to memoryless channels, zero-error capacity is the right figure of merit for achieving bounded estimation errors. We then consider finite-state, worst-case versions of the common erasure, and additive noise channels models, in which the noise is governed by a finite-state machine without any statistical structure. Upper and lower bounds on their zero-error capacities are derived, revealing a connection with the topological entropy of the channel dynamics. Separate necessary and sufficient conditions for bounded linear state estimation errors via such channels are obtained. These estimation conditions bring together the topological entropies of the linear system and the discrete channel. [ABSTRACT FROM AUTHOR]

This article considers the identification of finite-impulse response systems, where information about the inputs and outputs of the system undergoes quantization into binary values before transmission to the estimator. In the case where the thresholds of the input and output quantizers can be adapted, we propose identification schemes that are strongly consistent for Gaussian distributed inputs and noises. The algorithms are based on the idea that certain joint probabilities of the unquantized signals can be estimated from the binary signals, and the system parameters can then be inferred from these estimates. The algorithms and their properties are illustrated in simulation examples. [ABSTRACT FROM AUTHOR]

This paper studies the assessment of Granger causality between jointly Gaussian signals from binary/non-uniformly quantized measurements. A necessary and sufficient condition is proposed for Granger causality inference under binary quantization. Furthermore, sufficient conditions are introduced to infer Granger causality between jointly Gaussian signals through non-uniformly quantized measurements. No assumptions are made on the identifiability of the jointly Gaussian random processes through the quantized observations.

This paper investigates the assessment of Granger causality (GC) between jointly Gaussian signals based on noisy or filtered measurements. To do so, a recent rank condition for inferring GC between jointly Gaussian stochastic processes is exploited. Sufficient conditions are derived under which GC can be reliably inferred from the second order moments of the noisy or filtered measurements. This approach does not require a model of the underlying Gaussian system to be identified. The noise signals are not required to be Gaussian or independent, and the filters may be noncausal or nonminimum-phase, as long as they are stable.

A variety of resource allocation problems on networked systems, for example, those in cyber-physical systems or Internet-of-things applications, require distributed solution methods. Modern distributed algorithms usually require bandwidth-limited digital communication between the system and its users, who are often modeled as independent decision makers with individual preferences. This paper presents a quantitative information flow and knowledge gain analysis of decentralized iterative algorithms with bounded trajectories in the context of convex network utility maximization problems and strategic games with a unique Nash equilibrium solution. First, a novel generic framework is introduced to quantify knowledge gain in network resource allocation problems using entropy by taking into account priors in the solution space. Second, a general result is presented on the interplay between quantization of information and distributed algorithm performance both for linear and sublinear convergence. Third, information flow in distributed algorithms is studied and a lower bound is derived on the total amount of information exchanged for convergence under uniform quantization. The well-known primal–dual decomposition algorithm is used as an example to illustrate the results. Finally, convergence guarantees for distributed algorithms with estimation are investigated. This paper establishes specific links between information concepts and iterative algorithms in addition to building a foundation for integrating learning schemes into distributed optimization.

This paper investigates the asymptotic and nonasymptotic behavior of the quantized primal-dual (PD) algorithm in network utility maximization (NUM) problems, in which a group of agents maximizes the sum of their individual concave objective functions under linear constraints. In the asymptotic scenario, we use the information-theoretic notion of differential entropy power to establish universal bounds on the maximum exponential convergence rates of joint PD, primal and dual variables under optimum-achieving quantization schemes. These results provide tradeoffs between the speed of exponential convergence, the agents' objective functions, the communication bit rates, and the number of agents and constraints. In the nonasymptotic scenario, we obtain lower bounds on the mean square distance of joint PD, primal and dual variables from the optimal solution at any time instant. These bounds hold regardless of the quantization scheme used.

This paper investigates the impact of quantized inter-agent communications on the asymptotic and transient behavior of gradient-based Nash-seeking algorithms in non-cooperative games. Using the information-theoretic notion of entropy power, we establish a universal lower bound on the asymptotic rate of exponential mean-square convergence to the Nash equilibrium (NE). This bound depends on the inter-agent data rate and the local behavior of the agents' utility functions, and is independent of the quantizer structure. Next, we study transient performance and derive an upper bound on the average time required to settle inside a specified ball around the NE, under uniform quantization. Furthermore, we establish an upper bound on the probability that agents' actions lie outside this ball, and show that this bound decays double-exponentially with time. Finally, we propose an adaptive quantization scheme that allows the gradient algorithm to converge to the NE despite quantized inter-agent communications. [ABSTRACT FROM AUTHOR]

This paper studies the complexity of solving the class Gof all N-player non-cooperative games with continuous action spaces that admit at least one Nash equilibrium (NE). We consider a distributed Nash seeking setting where agents communicate with a set of system nodes (SNs), over noisy communication channels, to obtain the required information for updating their actions. The complexity of solving games in the class Gis defined as the minimum number of iterations required to find a NE of any game in Gwith ε accuracy. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving the game class Gthat depends on the Kolmogorov 2ε-capacity of the constraint set and the total capacity of the communication channels. We also derive a lower bound on the complexity of solving games in Gwhich depends on the volume and surface area of the constraint set.

A data rate theorem for stabilization of a linear, discrete-time, dynamical system with arbitrarily large disturbances, over a rate-limited, time-varying communication channel is presented. Necessary and sufficient conditions for stabilization are derived, their implications and relationships with related results in the literature are discussed. The proof techniques rely on both information-theoretic and control-theoretic tools. [ABSTRACT FROM AUTHOR]

It is well known in the field of dynamical systems that entropy can be defined rigorously for completely deterministic open-loop systems. However, such definitions have found limited application in engineering, unlike Shannon's statistical entropy. In this paper, it is shown that the problem of communication-limited stabilization is related to the concept of topological entropy, introduced by Adler et al. as a measure of the information rate of a continuous map on a compact topological space. Using similar open cover techniques, the notion of topological feedback entropy (TFE) is defined in this paper and proposed as a measure of the inherent rate at which a map on a noncompact topological space with inputs generates stability information. It is then proven that a topological dynamical plant can be stabilized into a compact set if and only if the data rate in the feedback loop exceeds the,TFE of the plant on the set. By taking appropriate limits in a metric space, the concept of local TFE (LTFE) is defined at fixed points of the plant, and it is shown that the plant is locally uniformly asymptotically stabilizable to a fixed point if and only if the data rate exceeds the plant LTFE at the fixed point. For continuously differentiable plants in Euclidean space, real Jordan forms and volume partitioning arguments are then used to derive an expression for LTFE in terms of the unstable eigenvalues of the fixed point Jacobian. [ABSTRACT FROM AUTHOR]

This paper considers the problem of estimating the state of a linear system via a digital link with a finite bit-rate R. Classical estimation theory does not apply here since the estimator only observes the transmitted sequence of finite-valued symbols. A new coder-estimator for linear systems with process and measurement noise is given. Provided that a certain inequality linking the bit-rate to the dynamical parameters is satisfied, and under very mild assumptions on the noise distributions, the expected absolute estimation error remains of the same order as in the classical situation with infinite bit-rate. In particular, if the classical estimation error approaches zero, then the finite bit-rate error goes to zero at exactly the same rate