Imitation learning (IL) is notably effective for robotic tasks where directly programming behaviors or defining optimal control costs is challenging. In this work, we address a scenario where the imitator relies solely on observed behavior and cannot make environmental interactions during learning. It does not have additional supplementary datasets beyond the expert's dataset nor any information about the transition dynamics. Unlike state-of-the-art (SOTA) IL methods, this approach tackles the limitations of conventional IL by operating in a more constrained and realistic setting. Our method uses the Markov balance equation and introduces a novel conditional density estimation-based imitation learning framework. It employs conditional normalizing flows for transition dynamics estimation and aims at satisfying a balance equation for the environment. Through a series of numerical experiments on Classic Control and MuJoCo environments, we demonstrate consistently superior empirical performance compared to many SOTA IL algorithms.

In this paper, we propose Posterior Sampling Reinforcement Learning for Zero-sum Stochastic Games (PSRL-ZSG), the first online learning algorithm that achieves Bayesian regret bound of $\tilde\mathcal{O}(HS\sqrt{AT})$ in the infinite-horizon zero-sum stochastic games with average-reward criterion. Here $H$ is an upper bound on the span of the bias function, $S$ is the number of states, $A$ is the number of joint actions and $T$ is the horizon. We consider the online setting where the opponent can not be controlled and can take any arbitrary time-adaptive history-dependent strategy. Our regret bound improves on the best existing regret bound of $\tilde\mathcal{O}(\sqrt[3]{DS^2AT^2})$ by Wei et al., (2017) under the same assumption and matches the theoretical lower bound in $T$.

Solving Partially Observable Markov Decision Processes (POMDPs) is hard. Learning optimal controllers for POMDPs when the model is unknown is harder. Online learning of optimal controllers for unknown POMDPs, which requires efficient learning using regret-minimizing algorithms that effectively tradeoff exploration and exploitation, is even harder, and no solution exists currently. In this paper, we consider infinite-horizon average-cost POMDPs with unknown transition model, though a known observation model. We propose a natural posterior sampling-based reinforcement learning algorithm (PSRL-POMDP) and show that it achieves a regret bound of $O(\log T)$, where $T$ is the time horizon, when the parameter set is finite. In the general case (continuous parameter set), we show that the algorithm achieves $O(T^{2/3})$ regret under two technical assumptions. To the best of our knowledge, this is the first online RL algorithm for POMDPs and has sub-linear regret.

Autonomous agents often operate in environments where the state is partially observed. In addition to maximizing their cumulative reward, agents must execute complex tasks with rich temporal and logical structures. These tasks can be expressed using temporal logic languages like finite linear temporal logic. This paper, for the first time, provides a structured framework for designing agent policies that maximize the reward while ensuring that the probability of satisfying the temporal logic specification is sufficiently high. We reformulate the problem as a constrained partially observable Markov decision process (POMDP) and provide a novel approach that can leverage off-the-shelf unconstrained POMDP solvers for solving it. Our approach guarantees approximate optimality and constraint satisfaction with high probability. We demonstrate its effectiveness by implementing it on several models of interest.

We study the problem of designing a dynamic mechanism for security management in an interconnected multi-agent system with N strategic agents and one coordinator. The system is modeled as a network of N vertices. Each agent resides in one of the vertices of the network and has a privately known security state that describes its safety level at each time. The evolution of an agent's security state depends on its own state, the states of its neighbors in the network and on actions taken by a network coordinator. Each agent's utility at time instant t depends on its own state, the states of its neighbors in the network and on actions taken by a network coordinator. The objective of the network coordinator is to take security actions in order to maximize the long-term expected social surplus. Since agents are strategic and their security states are private information, the coordinator needs to incentivize agents to reveal their information. This results in a dynamic mechanism design problem for the coordinator. We leverage the inter-temporal correlations between the agents' security states to identify sufficient conditions under which an incentive compatible expected social surplus maximizing mechanism can be constructed. We then identify two special cases of our formulation and describe how the desired mechanism is constructed in these cases.

The problem of verifying whether a multi-component system has anomalies or not is addressed. Each component can be probed over time in a data-driven manner to obtain noisy observations that indicate whether the selected component is anomalous or not. The aim is to minimize the probability of incorrectly declaring the system to be free of anomalies while ensuring that the probability of correctly declaring it to be safe is sufficiently large. This problem is modeled as an active hypothesis testing problem in the Neyman-Pearson setting. Component selection and inference strategies are designed and analyzed in the non-asymptotic regime. For a specific class of homogeneous problems, stronger (with respect to prior work) non-asymptotic converse and achievability bounds are provided.

Regret analysis is challenging in Multi-Agent Reinforcement Learning (MARL) primarily due to the dynamical environments and the decentralized information among agents. We attempt to solve this challenge in the context of decentralized learning in multi-agent linear-quadratic (LQ) dynamical systems. We begin with a simple setup consisting of two agents and two dynamically decoupled stochastic linear systems, each system controlled by an agent. The systems are coupled through a quadratic cost function. When both systems’ dynamics are unknown and there is no communication among the agents, we show that no learning policy can generate sub-linear in $T$ regret, where $T$ is the time horizon. When only one system’s dynamics are unknown and there is one-directional communication from the agent controlling the unknown system to the other agent, we propose a MARL algorithm based on the construction of an auxiliary single-agent LQ problem. The auxiliary single-agent problem in the proposed MARL algorithm serves as an implicit coordination mechanism among the two learning agents. This allows the agents to achieve a regret within $O(\sqrt{T})$ of the regret of the auxiliary single-agent problem. Consequently, using existing results for single-agent LQ regret, our algorithm provides a $\tilde{O}(\sqrt{T})$ regret bound. (Here $\tilde{O}(\cdot)$ hides constants and logarithmic factors). Our numerical experiments indicate that this bound is matched in practice. From the two-agent problem, we extend our results to multi-agent LQ systems with certain communication patterns which appear in vehicle platoon control.

An active hypothesis testing problem is formulated. In this problem, the agent can perform a fixed number of experiments and then decide on one of the hypotheses. The agent is also allowed to declare its experiments inconclusive if needed. The objective is to minimize the probability of making an incorrect inference (misclassification probability) while ensuring that the true hypothesis is declared conclusively with moderately high probability. For this problem, lower and upper bounds on the optimal misclassification probability are derived and these bounds are shown to be asymptotically tight. In the analysis, a sub-problem, which can be viewed as a generalization of the Chernoff-Stein lemma, is formulated and analyzed. A heuristic approach to strategy design is proposed and its relationship with existing heuristic strategies is discussed.

Coded caching can significantly reduce the communication bandwidth requirement for satisfying users' demands by utilizing the multicasting gain among multiple users. Most existing works assume that the users follow the prescriptions for content placement made by the system. However, users may prefer to decide what files to cache. To address this issue, we consider a network consisting of a file server connected through a shared link to K users, each equipped with a cache which has been already filled arbitrarily. Given an arbitrary content placement, the goal is to find a delivery strategy for the server that minimizes the load of the shared link. In this paper, we focus on a specific class of coded multicasting delivery schemes known as the “clique cover delivery scheme.” We first formulate the optimal clique cover delivery problem as a combinatorial optimization problem. Using a connection with the weighted set cover problem, we propose an approximation algorithm and show that it provides an approximation ratio of (1 + log K), while the approximation ratio for the existing coded delivery schemes is linear in K. Numerical simulations show that our proposed algorithm provides a considerable bandwidth reduction over the existing coded delivery schemes for almost all content placement schemes.

A new class of caching schemes, called coded caching, can significantly reduce the communication bandwidth requirement for satisfying users' demands by utilizing the multicasting gain among multiple users. Most existing works assume that the users follow the prescriptions for content placement made by the system. However, users may prefer to decide what files to cache or discard some part of their caches due to lack of space. In order to address this issue, we study a caching system where the content placement phase has been already carried out by the users arbitrarily. More specifically, we consider a network consisting of a file server connected through a shared link to $K$ users, each equipped with a cache. Given arbitrary content placement by the users, the goal is to find a coded multicast strategy for the server that minimizes the load of the shared link. We first formulate the optimal coded multicast design problem as an Integer Linear Program (ILP). Using a connection with the weighted set cover problem, we propose an approximation algorithm for solving this problem. We show that our proposed algorithm provides $(1 + \log K)$-approximation for the optimal coded multicast design problem, while the approximation ratio for the existing coded delivery schemes is linear in $K$. Numerical simulations show that our proposed algorithm provides a considerable bandwidth reduction over the existing coded delivery schemes for uniformly-random generated content placement.

The problem of designing a profit-maximizing, Bayesian incentive compatible and individually rational mechanism with flexible consumers and costly heterogeneous supply is considered. In our setup, each consumer is associated with a flexibility set that describes the subset of goods the consumer is equally interested in. Each consumer wants to consume one good from its flexibility set. The flexibility set of a consumer and the utility it gets from consuming a good from its flexibility set are its private information. We adopt the flexibility model of [1] and focus on the case of nested flexibility sets - each consumer's flexibility set can be one of k nested sets. Examples of settings with this inherent nested structure are provided. On the supply side, we assume that the seller has an initial stock of free supply but it can purchase more goods for each of the nested sets at fixed exogenous prices. We characterize the allocation and purchase rules for a profit-maximizing, Bayesian incentive compatible and individually rational mechanism as the solution to an integer program. The optimal payment function is pinned down by the optimal allocation rule in the form of an integral equation. We show that the nestedness of flexibility sets can be exploited to obtain a simple description of the optimal allocations, purchases and payments in terms of thresholds that can be computed through a straightforward iterative procedure.

We consider the problem of learning an unknown Markov Decision Process (MDP) that is weakly communicating in the infinite horizon setting. We propose a Thompson Sampling-based reinforcement learning algorithm with dynamic episodes (TSDE). At the beginning of each episode, the algorithm generates a sample from the posterior distribution over the unknown model parameters. It then follows the optimal stationary policy for the sampled model for the rest of the episode. The duration of each episode is dynamically determined by two stopping criteria. The first stopping criterion controls the growth rate of episode length. The second stopping criterion happens when the number of visits to any state-action pair is doubled. We establish $\tilde O(HS\sqrt{AT})$ bounds on expected regret under a Bayesian setting, where $S$ and $A$ are the sizes of the state and action spaces, $T$ is time, and $H$ is the bound of the span. This regret bound matches the best available bound for weakly communicating MDPs. Numerical results show it to perform better than existing algorithms for infinite horizon MDPs.

In the above titled paper (ibid., vol. 57. no. 8, pp. 5410-5435, Aug. 2011), a correction to the second sentence after equation (4) in Section II is necessary. The correction is presented here.

Sequential problems in decentralized detection are considered. Peripheral sensors make repeated noisy observations of a binary hypothesis. At each time, a peripheral sensor has to decide whether to stop and send a final binary message to a coordinating sensor/fusion center or to continue taking costly measurements. The coordinating sensor's operation is explored under two different scenarios. In the first scenario, the coordinating sensor waits to receive the final message from each of the peripheral sensors and then starts taking costly measurements of its own. The coordinating sensor is then faced with a stopping problem on whether to stop and declare a decision on the hypothesis or to continue taking measurements. In the second scenario, the coordinating sensor starts taking measurements from the beginning, without waiting for the final messages from the peripheral sensors. At any time, the coordinating sensor has to decide whether to stop and declare a decision on the hypothesis or to continue to take more measurements and wait for the peripheral sensors to send their final message. Parametric characterization of optimal policies for the peripheral and the coordinating sensors are obtained under both scenarios. A sequential methodology for finding the optimal policies is presented.

A real-time communication system with two encoders communicating with a single receiver over separate noisy channels is considered. The two encoders make distinct partial observations of a Markov source. Each encoder must encode its observations into a sequence of discrete symbols. The symbols are transmitted over noisy channels to a finite memory receiver that attempts to reconstruct some function of the state of the Markov source. Encoding and decoding must be done in real-time, that is, the distortion measure does not tolerate delays. Under the assumption that the encoders' observations are conditionally independent Markov chains given an unobserved time-invariant random variable, results on the structure of optimal real-time encoding and decoding functions are obtained. It is shown that there exist finite-dimensional sufficient statistics for the encoders. The problem with noiseless channels and perfect memory at the receiver is then considered. A new methodology to find the structure of optimal real-time encoders is employed. A sufficient statistic with a time-invariant domain is found for this problem. This methodology exploits the presence of common information between the encoders and the receiver when communication is over noiseless channels.

In this paper, we consider the problem of monitoring soil moisture evolution using a wireless network of in situ sensors. Continuously sampling moisture levels with these sensors incurs high-maintenance and energy consumption costs, which are particularly undesirable for wireless networks. Our main hypothesis is that a sparser set of measurements can meet the monitoring objectives in an energy-efficient manner. The underlying idea is that we can trade off some inaccuracy in estimating soil moisture evolution for a significant reduction in energy consumption. We investigate how to dynamically schedule the sensor measurements so as to balance this tradeoff. Unlike many prior studies on sensor scheduling that make generic assumptions on the statistics of the observed phenomenon, we obtain statistics of soil moisture evolution from a physical model. We formulate the optimal measurement scheduling and estimation problem as a partially observable Markov decision problem (POMDP). We then utilize special features of the problem to approximate the POMDP by a computationally simpler finite-state Markov decision problem (MDP). The result is a scalable, implementable technology that we have tested and validated numerically and in the field.

We consider a sequential problem in decentralized detection. Two observers can make repeated noisy observations of a binary hypothesis on the state of the environment. At any time, observer 1 can stop and send a final message to observer 2 or it may continue to take more measurements. Every time observer 1 postpones its final message to observer 2, it incurs a penalty. We consider observer 2's operation under two different scenarios. In the first scenario, observer 2 waits to receive the final message from observer 1 and then starts taking measurements of its own. It is then faced with a stopping problem on whether to stop and declare a decision on the hypothesis or to continue taking measurements. In the second scenario, observer 2 starts taking measurements from the beginning. It is then faced with a different stopping problem. At any time, observer 2 can decide whether to stop and declare a decision on the hypothesis or to continue to take more measurements and wait for observer 1 to send its final message. We obtain parametric characterization of optimal policies for the two observers under both scenarios. We then extend these characterizations to a problem with multiple peripheral sensors that each send a single final message to a coordinating sensor who makes the final decision on the hypothesis.

We have developed a new concept for a smart sensor web technology for measurements of soil moisture that include spaceborne and in-situ assets. The objective of the technology is to enable a guided/adaptive sampling strategy for the in-situ sensor network to meet the measurement validation objectives of the spaceborne sensors with respect to resolution and accuracy. One potential application is the Soil Moisture Active/Passive (SMAP) mission. The science measurements considered are the surface-to-depth profiles of soil moisture estimated from satellite radars and radiometers, with calibration and validation using in-situ sensors. Installing an in-situ network to sample the field for all ranges of variability is impractical. However, a sparser but smarter network can provide the validation estimates by operating in a guided fashion with guidance from its own sparse measurements. The feedback and control take place in the context of a dynamic data assimilation system subject to energy and accuracy constraints. The overall design of the smart sensor web including the control architecture, assimilation framework, and actuation hardware are presented in this paper. We also present results of initial numerical and laboratory demonstrations of the sensor web concept, which includes a small number of soil moisture.