Search

When making decisions in a network, it is important to have up-to-date knowledge of the current state of the system. Obtaining this information, however, comes at a cost. In this paper, we determine the optimal finite-time update policy for monitoring the binary states of remote sources with a reporting rate constraint. We first prove an upper and lower bound of the minimal probability of error before solving the problem analytically. The error probability is defined as the probability that the system performs differently than it would with full system knowledge. More specifically, an error occurs when the destination node incorrectly determines which top-K priority sources are in the ``free'' state. We find that the optimal policy follows a specific ordered 3-stage update pattern. We then provide the optimal transition points for each stage for each source., Comment: Accepted at ISIT 2024

Importance sampling is a central idea underlying off-policy prediction in reinforcement learning. It provides a strategy for re-weighting samples from a distribution to obtain unbiased estimates under another distribution. However, importance sampling weights tend to exhibit extreme variance, often leading to stability issues in practice. In this work, we consider a broader class of importance weights to correct samples in off-policy learning. We propose the use of $\textit{value-aware importance weights}$ which take into account the sample space to provide lower variance, but still unbiased, estimates under a target distribution. We derive how such weights can be computed, and detail key properties of the resulting importance weights. We then extend several reinforcement learning prediction algorithms to the off-policy setting with these weights, and evaluate them empirically., Comment: CoLLAs 2023

A central challenge to applying many off-policy reinforcement learning algorithms to real world problems is the variance introduced by importance sampling. In off-policy learning, the agent learns about a different policy than the one being executed. To account for the difference importance sampling ratios are often used, but can increase variance in the algorithms and reduce the rate of learning. Several variations of importance sampling have been proposed to reduce variance, with per-decision importance sampling being the most popular. However, the update rules for most off-policy algorithms in the literature depart from per-decision importance sampling in a subtle way; they correct the entire TD error instead of just the TD target. In this work, we show how this slight change can be interpreted as a control variate for the TD target, reducing variance and improving performance. Experiments over a wide range of algorithms show this subtle modification results in improved performance., Comment: 5 pages, 2 figures

A variety of theoretically-sound policy gradient algorithms exist for the on-policy setting due to the policy gradient theorem, which provides a simplified form for the gradient. The off-policy setting, however, has been less clear due to the existence of multiple objectives and the lack of an explicit off-policy policy gradient theorem. In this work, we unify these objectives into one off-policy objective, and provide a policy gradient theorem for this unified objective. The derivation involves emphatic weightings and interest functions. We show multiple strategies to approximate the gradients, in an algorithm called Actor Critic with Emphatic weightings (ACE). We prove in a counterexample that previous (semi-gradient) off-policy actor-critic methods--particularly Off-Policy Actor-Critic (OffPAC) and Deterministic Policy Gradient (DPG)--converge to the wrong solution whereas ACE finds the optimal solution. We also highlight why these semi-gradient approaches can still perform well in practice, suggesting strategies for variance reduction in ACE. We empirically study several variants of ACE on two classic control environments and an image-based environment designed to illustrate the tradeoffs made by each gradient approximation. We find that by approximating the emphatic weightings directly, ACE performs as well as or better than OffPAC in all settings tested., Comment: 63 pages

This work establishes that the physical layer can be used to perform information-theoretic authentication in additive white Gaussian noise channels, as long as the adversary is not omniscient. The model considered consists of an encoder, decoder, and adversary, where the adversary has access to the message, a non-causal noisy observation of the encoder's transmission, and unlimited transmission power, while the decoder observes a noisy version of the sum of the encoder and adversary's outputs. A method to modify a generic existing channel code to enable authentication is presented. It is shown that this modification costs an asymptotically negligible amount of the coding rate, while still enabling authentication as long as the adversary's observation is not noiseless. Also notable is that this modification is not (asymptotically) a function of the statistical characterization of the adversary's channel and furthermore no secret key is required, hence paving the way for a robust practical implementation. Using these results, the channel-authenticated capacity is calculated and shown to be equal to the non-adversarial channel capacity. While this modular scheme is designed for use in the given channel model, it is applicable to a wide range of settings., Comment: Submitted for possible publication

We consider keyless authentication for point-to-point communication in the presence of a myopic adversary. In particular, the adversary has access to a non-causal noisy version of the transmission and may use this knowledge to choose the channel state of an arbitrarily-varying channel between legitimate users; the receiver is successful if it either decodes to the correct message or correctly detects adversarial interference. We show that a channel condition called U-overwritability, which allows the adversary to make its false message appear legitimate and untampered with, is a sufficient condition for zero authentication capacity. We present a useful way to compare adversarial channels, and show that once an AVC becomes U-overwritable, it remains U-overwritable for all "less myopic" adversaries. Finally, we show that stochastic encoders are necessary for positive authentication capacity in some cases, and examine in detail a binary adversarial channel that illustrates this necessity. Namely, for this binary channel, we show that when the adversarial channel is degraded with respect to the main channel between users, the no-adversary capacity of the underlying channel is achievable with a deterministic encoder. Otherwise, provided the channel to the adversary is not perfect, a stochastic encoder is necessary for positive authentication capacity; if such an encoder is allowed, the no-adversary capacity is again achievable., Comment: 22 pages; minor changes to notation and proofs of technical lemmas, results unchanged

This paper investigates the secret key authentication capacity region. Specifically, the focus is on a model where a source must transmit information over an adversary controlled channel where the adversary, prior to the source's transmission, decides whether or not to replace the destination's observation with an arbitrary one of their choosing (done in hopes of having the destination accept a false message). To combat the adversary, the source and destination share a secret key which they may use to guarantee authenticated communications. The secret key authentication capacity region here is then defined as the region of jointly achievable message rate, authentication rate, and key consumption rate (i.e., how many bits of secret key are needed). This is the first of a two part study, with the parts differing in how the authentication rate is measured. In this first study the authenticated rate is measured by the traditional metric of the maximum expected probability of false authentication. For this metric, we provide an inner bound which improves on those existing in the literature. This is achieved by adopting and merging different classical techniques in novel ways. Within these classical techniques, one technique derives authentication capability directly from the noisy communications channel, and the other technique derives its' authentication capability directly from obscuring the source., Comment: First of a two part paper. Large text overlap in introductions. Submitted for possible publication

This paper investigates the secret key authentication capacity region. Specifically, the focus is on a model where a source must transmit information over an adversary controlled channel where the adversary, prior to the source's transmission, decides whether or not to replace the destination's observation with an arbitrary one of their choosing (done in hopes of having the destination accept a false message). To combat the adversary, the source and destination share a secret key which they may use to guarantee authenticated communications. The secret key authentication capacity region here is then defined as the region of jointly achievable message rate, authentication rate, and key consumption rate (i.e., how many bits of secret key are needed). This is the second of a two part study, with the studies separated by how the authentication rate is measured. Here, the authentication rate is measured by the minimum of the maximum probability of false acceptance where the minimization is over all highly probable subsets of observations at the adversary. That is, consider the maximum probability of false authentication as a function of the adversary's observation, and the adversary's observation as a random variable. The authentication rate is then measured as the smallest number for which the probability that the maximum probability of false authentication is greater than said number is arbitrary small. This is termed typical authentication, since it only needs to consider adversarial observations which are typical with the transmission. Under this measure of authentication matching inner and outer bounds are determined., Comment: Second of a two part paper. Large text overlap in introductions. Submitted for possible publication

A basic information theoretic model for summarization is formulated. Here summarization is considered as the process of taking a report of $v$ binary objects, and producing from it a $j$ element subset that captures most of the important features of the original report, with importance being defined via an arbitrary set function endemic to the model. The loss of information is then measured by a weight average of variational distances, which we term the semantic loss. Our results include both cases where the probability distribution generating the $v$-length reports are known and unknown. In the case where it is known, our results demonstrate how to construct summarizers which minimize the semantic loss. For the case where the probability distribution is unknown, we show how to construct summarizers whose semantic loss when averaged uniformly over all possible distribution converges to the minimum., Comment: 9 pages, 2 figures. Extended version of ISIT submission

We construct a modular scheme which extends codes for wiretap channels of type I for use in wiretap channels of type II. This is done by using a concatenate and permute strategy, wherein multiple uses of the wiretap type I code are concatenated and then the joint sequence of symbols permuted. The choice of permutation is then encoded with a short code and appended to the transmitted sequence. Analysis shows essentially no degradation in operational parameters (rate, error rate, leakage) for the new code over the wiretap type II channel when compared to those of multiple uses of the original code over the wiretap type I channel., Comment: Extended version of ISIT submission, 7 pages

Policy gradient methods are widely used for control in reinforcement learning, particularly for the continuous action setting. There have been a host of theoretically sound algorithms proposed for the on-policy setting, due to the existence of the policy gradient theorem which provides a simplified form for the gradient. In off-policy learning, however, where the behaviour policy is not necessarily attempting to learn and follow the optimal policy for the given task, the existence of such a theorem has been elusive. In this work, we solve this open problem by providing the first off-policy policy gradient theorem. The key to the derivation is the use of $emphatic$ $weightings$. We develop a new actor-critic algorithm$\unicode{x2014}$called Actor Critic with Emphatic weightings (ACE)$\unicode{x2014}$that approximates the simplified gradients provided by the theorem. We demonstrate in a simple counterexample that previous off-policy policy gradient methods$\unicode{x2014}$particularly OffPAC and DPG$\unicode{x2014}$converge to the wrong solution whereas ACE finds the optimal solution., Comment: Updated to final NeurIPS version

This work constructs a discrete random variable that, when conditioned upon, ensures information stability of quasi-images. Using this construction, a new methodology is derived to obtain information theoretic necessary conditions directly from operational requirements. In particular, this methodology is used to derive new necessary conditions for keyed authentication over discrete memoryless channels and to establish the capacity region of the wiretap channel, subject to finite leakage and finite error, under two different secrecy metrics. These examples establish the usefulness of the proposed methodology., Comment: Submitted for possible publication

The rate regions of many variations of the standard and wire-tap channels have been thoroughly explored. Secrecy capacity characterizes the loss of rate required to ensure that the adversary gains no information about the transmissions. Authentication does not have a standard metric, despite being an important counterpart to secrecy. While some results have taken an information-theoretic approach to the problem of authentication coding, the full rate region and accompanying trade-offs have yet to be characterized. In this paper, we provide an inner bound of achievable rates with an average authentication and reliability constraint. The bound is established by combining and analyzing two existing authentication schemes for both noisy and noiseless channels. We find that our coding scheme improves upon existing schemes.

This paper employs equal-image-size source partitioning techniques to derive the capacities of the general discrete memoryless wiretap channel (DM-WTC) under four different secrecy criteria. These criteria respectively specify requirements on the expected values and tail probabilities of the differences, in absolute value and in exponent, between the joint probability of the secret message and the eavesdropper's observation and the corresponding probability if they were independent. Some of these criteria reduce back to the standard leakage and variation distance constraints that have been previously considered in the literature. The capacities under these secrecy criteria are found to be different when non-vanishing error and secrecy tolerances are allowed. Based on these new results, we are able to conclude that the strong converse property generally holds for the DM-WTC only under the two secrecy criteria based on constraining the tail probabilities. Under the secrecy criteria based on the expected values, an interesting phase change phenomenon is observed as the tolerance values vary., Comment: Published in proceedings of ISIT2017, contains a correction in result statements

If Alice must communicate with Bob over a channel shared with the adversarial Eve, then Bob must be able to validate the authenticity of the message. In particular we consider the model where Alice and Eve share a discrete memoryless multiple access channel with Bob, thus allowing simultaneous transmissions from Alice and Eve. By traditional random coding arguments, we demonstrate an inner bound on the rate at which Alice may transmit, while still granting Bob the ability to authenticate. Furthermore this is accomplished in spite of Alice and Bob lacking a pre-shared key, as well as allowing Eve prior knowledge of both the codebook Alice and Bob share and the messages Alice transmits., Comment: Pre-print. Paper presented at ITW 2016 Cambridge

This paper introduces equal-image-size source partitioning, a new tool for analyzing channel and joint source-channel coding in a multi-terminal discrete memoryless channel environment. Equal-image-size source partitioning divides the source (combination of messages and codewords) into a sub-exponential number of subsets. Over each of these subsets, the exponential orders of the minimum image sizes of most messages are roughly equal to the same entropy term. This property gives us the strength of minimum image sizes and the flexibility of entropy terms. Using the method of equal-image-size source partitioning, we prove separate necessary conditions for the existence of average-error and maximum-error codes. These necessary conditions are much stronger than the standard Fano's inequality, and can be weakened to render versions of Fano's inequality that apply to codes with non-vanishing error probabilities. To demonstrate the power of this new tool, we employ the stronger average-error version of Fano's inequality to prove the strong converse for the discrete memoryless wiretap channel with decaying leakage, which heretofore has been an open problem., Comment: Submitted to IEEE trans info theory. Presented in part at the 2014 International Symposium on Information Theory (ISIT) in Honolulu, HI, USA. 29 pages, 1 example. Comments welcome. This version fixes a mistake in the application example and corrects a number of typos

In this paper we investigate the image size characterization problem. We show that any arbitrary source set may be decomposed into sets whose image size characterization is the same as its entropy characterization. We also show that the number of these sets required is small enough that one may consider that from a coding perspective the achievable entropy region and achievable exponent region are equal. This has an impact on many source networks and network problems whose solution heretofore could not have the image size characterization applied to them., Comment: 5 Pages, ISIT 14

This paper presents a random coding scheme with which two nodes can exchange information with guaranteed integrity over a two-way Byzantine relay. This coding scheme is employed to obtain an inner bound on the capacity region with guaranteed information integrity. No pre-shared secret or secret transmission is needed for the proposed scheme. Hence the inner bound obtained is generally larger than those achieved based on secret transmission schemes. This approach advocates the separation of supporting information integrity and secrecy., Comment: 5 Pages, submitted to ISIT 2013

This paper studies the problem of detecting a potential malicious relay node by a source node that relies on the relay to forward information to other nodes. The channel model of two source nodes simultaneously sending symbols to a relay is considered. The relay is contracted to forward the symbols that it receives back to the sources in the amplify-and-forward manner. However there is a chance that the relay may send altered symbols back to the sources. Each source attempts to individually detect such malicious acts of the relay by comparing the empirical distribution of the symbols that it receives from the relay conditioned on its own transmitted symbols with known stochastic characteristics of the channel. It is shown that maliciousness of the relay can be asymptotically detected with sufficient channel observations if and only if the channel satisfies a non-manipulable condition, which can be easily checked. As a result, the non-manipulable condition provides us a clear-cut criterion to determine the detectability of the aforementioned class of symbol manipulation attacks potentially conducted by the relay., Comment: 25 pages, 9 figures. Math