In reinforcement learning for partially observable environments, many successful algorithms have been developed within the asymmetric learning paradigm. This paradigm leverages additional state information available at training time for faster learning. Although the proposed learning objectives are usually theoretically sound, these methods still lack a precise theoretical justification for their potential benefits. We propose such a justification for asymmetric actor-critic algorithms with linear function approximators by adapting a finite-time convergence analysis to this setting. The resulting finite-time bound reveals that the asymmetric critic eliminates error terms arising from aliasing in the agent state.

Leveraging large language models (LLMs) through prompting presents a cost-effective approach to build scalable systems without traditional model training. This paper showcases the effectiveness of using simple few-shot LLM prompt to develop a scalable and easily maintainable system that addresses a real-world user need. A critical user journey in video recommendation is watching serial content, which requires viewing episodes in a specific sequence. The existing method on YouTube for identifying serial content relied on manual creator tagging of playlists or inflexible regular expressions. These methods proved difficult to maintain and scale, limiting the system's ability to effectively identify and recommend serial content. This paper demonstrates that a carefully designed few-shot LLM prompt can accurately identify serial playlists at scale, improving user experience with minimal engineering. The paper details the challenges and lessons learned in developing and deploying this prompting-based system.

In this paper, we investigate the concentration properties of cumulative reward in Markov Decision Processes (MDPs), focusing on both asymptotic and non-asymptotic settings. We introduce a unified approach to characterize reward concentration in MDPs, covering both infinite-horizon settings (i.e., average and discounted reward frameworks) and finite-horizon setting. Our asymptotic results include the law of large numbers, the central limit theorem, and the law of iterated logarithms, while our non-asymptotic bounds include Azuma-Hoeffding-type inequalities and a non-asymptotic version of the law of iterated logarithms. Additionally, we explore two key implications of our results. First, we analyze the sample path behavior of the difference in rewards between any two stationary policies. Second, we show that two alternative definitions of regret for learning policies proposed in the literature are rate-equivalent. Our proof techniques rely on a martingale decomposition of cumulative reward, properties of the solution to the policy evaluation fixed-point equation, and both asymptotic and non-asymptotic concentration results for martingale difference sequences.

Human cognitive states, such as mental workload, play a pivotal role in decision making processes within human automation teams. Although subjective measures of mental workload can be obtained using standard questionnaires, such as the NASA-TLX, their administration is often impractical as it interferes with the primary tasks of the human operator. Therefore, it is of interest to estimate these subjective measures from less intrusive observations. Evidence suggests that mental workload is a dynamic process so incorporating historical measurements could reduce its estimation error. In addition, the estimation of operator performance in human automation teams is essential in optimizing task effectiveness and facilitating efficient resource allocation. In this work, we consider a scenario where a human and an automation solve binary classification tasks under time constraints. We present and compare different dynamic schemes to estimate the operator’s performance, i.e., classification accuracy, and its subjective ratings on subscales of the NASA-TLX questionnaire, which measure mental workload across multiple dimensions. These schemes differ in the information available for estimation. We test these schemes on data collected from a scenario, where a human and an automation perform a series of classification tasks for simulated mobile objects. Our analysis of the interaction data and the estimation schemes indicates that employing dynamic estimation for certain NASA-TLX subscale ratings leads to decreased estimation errors.

Reinforcement learning (RL) folklore suggests that methods of function approximation based on history, such as recurrent neural networks or state abstractions that include past information, outperform those without memory, because function approximation in Markov decision processes (MDP) can lead to a scenario akin to dealing with a partially observable MDP (POMDP). However, formal analysis of history-based algorithms has been limited, with most existing frameworks concentrating on features without historical context. In this paper, we introduce a theoretical framework to examine the behaviour of RL algorithms that control an MDP using feature abstraction mappings based on historical data. Additionally, we leverage this framework to develop a practical RL algorithm and assess its performance across various continuous control tasks.

Representations are at the core of all deep reinforcement learning (RL) methods for both Markov decision processes (MDPs) and partially observable Markov decision processes (POMDPs). Many representation learning methods and theoretical frameworks have been developed to understand what constitutes an effective representation. However, the relationships between these methods and the shared properties among them remain unclear. In this paper, we show that many of these seemingly distinct methods and frameworks for state and history abstractions are, in fact, based on a common idea of self-predictive abstraction. Furthermore, we provide theoretical insights into the widely adopted objectives and optimization, such as the stop-gradient technique, in learning self-predictive representations. These findings together yield a minimalist algorithm to learn self-predictive representations for states and histories. We validate our theories by applying our algorithm to standard MDPs, MDPs with distractors, and POMDPs with sparse rewards. These findings culminate in a set of preliminary guidelines for RL practitioners.

The standard approach for Partially Observable Markov Decision Processes (POMDPs) is to convert them to a fully observed belief-state MDP. However, the belief state depends on the system model and is therefore not viable in reinforcement learning (RL) settings. A widely used alternative is to use an agent state, which is a model-free, recursively updateable function of the observation history. Examples include frame stacking and recurrent neural networks. Since the agent state is model-free, it is used to adapt standard RL algorithms to POMDPs. However, standard RL algorithms like Q-learning learn a stationary policy. Our main thesis that we illustrate via examples is that because the agent state does not satisfy the Markov property, non-stationary agent-state based policies can outperform stationary ones. To leverage this feature, we propose PASQL (periodic agent-state based Q-learning), which is a variant of agent-state-based Q-learning that learns periodic policies. By combining ideas from periodic Markov chains and stochastic approximation, we rigorously establish that PASQL converges to a cyclic limit and characterize the approximation error of the converged periodic policy. Finally, we present a numerical experiment to highlight the salient features of PASQL and demonstrate the benefit of learning periodic policies over stationary policies.

We propose a theoretical framework for approximate planning and learning in partially observed systems. Our framework is based on the fundamental notion of information state. We provide two definitions of information state---i) a function of history which is sufficient to compute the expected reward and predict its next value; ii) a function of the history which can be recursively updated and is sufficient to compute the expected reward and predict the next observation. An information state always leads to a dynamic programming decomposition. Our key result is to show that if a function of the history (called AIS) approximately satisfies the properties of the information state, then there is a corresponding approximate dynamic program. We show that the policy computed using this is approximately optimal with bounded loss of optimality. We show that several approximations in state, observation and action spaces in literature can be viewed as instances of AIS. In some of these cases, we obtain tighter bounds. A salient feature of AIS is that it can be learnt from data. We present AIS based multi-time scale policy gradient algorithms and detailed numerical experiments with low, moderate and high dimensional environments.

Mobile Edge Computing (MEC) refers to the concept of placing computational capability at the edge of the network to reduce the latency in handling the client requests. The performance of an edge server is adversely affected when it is overloaded, especially if it crashes due to overload and causes service failures. In this paper, a solution to prevent node from getting overloaded is analyzed by introducing an admission control policy. An adaptive admission control policy based low complexity RL (Reinforcement Learning) SALMUT (Structure-Aware Learning for Multiple Thresholds) is validated using several scenarios mimicking real world deployments. This approach performs as well as to the state-of-the-art deep RL algorithms such as PPO (Proximal Policy Optimization) and A2C (Advantage Actor Critic), but requires an order of magnitude less time to train, and outputs easily interpretable policy.

This paper develops a coverage-centric adaptive path planner to visually survey a planar environment. This is achieved by modifying an existing path planning architecture to use a novel coverage estimation approach called convolved coverage estimation (CCE). The planner maximizes the probability of terrain coverage and exploits terrain features for loop closure to keep path uncertainty in check. The developed algorithm considers multi-dimensional uncertainty, operates in real-time, and does not require external correction methods like GPS. These characteristics are validated in high-fidelity simulation and flight tests on an unmanned aerial vehicle (UAV).

Smart-metering systems report electricity usage of a user to the utility provider on almost real-time basis. This could leak private information about the user to the utility provider. In this paper, we investigate the use of a rechargeable battery in order to provide privacy to the user. We assume that the user load sequence is a first-order Markov process, the battery satisfies ideal charge conservation, and that privacy is measured using normalized mutual information (leakage rate) between the user load and the battery output. We study the optimal battery charging policy that minimizes the leakage rate among the class of battery policies that satisfy causality and charge conservation. We propose a series reduction on the original problem and ultimately recast it as a Markov Decision Process (MDP) that can be solved using a dynamic program. In the special case of i.i.d. demand, we explicitly characterize the optimal policy and show that the associated leakage rate can be expressed as a single-letter mutual information expression. In this case, we show that the optimal charging policy admits an intuitive interpretation of preserving a certain invariance property of the state. Interestingly an alternative proof of optimality can be provided that does not rely on the MDP approach, but is based on purely information theoretic reductions.

Reliability in integrated circuits is becoming a critical issue with the miniaturization of electronics. Smaller process technologies have led to higher power densities, resulting in higher temperatures and earlier device wear-out. One way to mitigate failure is by over-provisioning resources and remapping tasks from failed components to components with spare capacity, or slack. Since the slack allocation design space is large, finding the optimal is difficult, as brute-force approaches are impractical. During design space exploration, device lifetimes are typically evaluated using Monte-Carlo Simulation (MCS) by sampling each design equally; this method is inefficient since poor designs are evaluated as accurately as good designs. A better method will focus sampling time on the designs that are difficult to distinguish, reducing the time required to evaluate a set of designs; this can be accomplished using Multi-armed Bandit (MAB) Algorithms. This work demonstrates that MAB achieve the same level of accuracy as MCS in 1.45 to 5.26 times fewer samples.

We investigate remote estimation over a Gilbert-Elliot channel with feedback. The channel is modelled as an ON/OFF channel, where the state of the channel evolves as a Markov chain. The channel state is observed by the receiver and fed back to the transmitter with one unit delay. In addition, the transmitter gets ACK/NACK feedback for successful/unsuccessful transmission. Using ideas from team theory, we establish the structure of optimal transmission and estimation strategies and identify a dynamic program to determine optimal strategies with that structure. We then consider first-order autoregressive sources where the noise process has unimodal and symmetric distribution. Using ideas from majorization theory, we show that the optimal transmission strategy has a threshold structure and the optimal estimation strategy is Kalman-filter like.

The problem of assigning priorities for scheduling multiple sensor measurements over a control area network is considered. A dynamic priority allocation scheme is proposed, where priorities are assigned according to the value of information. The value of information is defined as the fee a receiver is willing to pay to access that information. It is shown that the value of information can be computed by solving two Fredholm integral equations. An efficient computation of the value of information is proposed. Numerical examples suggest that the proposed priority assignment scheme outperforms the existing schemes in the literature.

In this paper we consider an interactive communication system with two users, who sequentially observe two correlated sources, and send the quantized observation symbol to each other. The sources are functions of a random variable, which the users wish to estimate. The transmission is costly and the fidelity of reconstruction is measured by a distortion function. We model this problem using dynamic team theory. The two users are viewed as two decision makers that have access to different information but need to coordinate their actions to minimize a common objective. Through a series of simplifications, we identify time-homogeneous information states (sufficient statistics) for the encoding and decoding strategies and a dynamic programming decomposition to compute the optimal strategies.

The problem of optimal real-time transmission of a Gauss-Markov source under constraints on the expected number of transmissions is considered. This setup is motivated by applications where transmission is sporadic and the cost of switching on the radio and transmitting is significantly more important than the size of the transmitted data packet. The structure of optimal transmission and estimation strategies had been established in the literature. We use these structural results to determine the distortion-transmission function, i.e., the minimum expected distortion that can be achieved when the expected number of transmissions is less than or equal to a particular value. We characterize how the distortion-transmission function scales with the variance of the source and show that it can be computed numerically by solving two Fredholm integral equations of the second kind.

The problem of optimal real-time transmission of a Markov source under constraints on the expected number of transmissions is considered, both for the discounted and long term average cases. This setup is motivated by applications where transmission is sporadic and the cost of switching on the radio and transmitting is significantly more important than the size of the transmitted data packet. For this model, we characterize the distortion-transmission function, i.e., the minimum expected distortion that can be achieved when the expected number of transmissions is less than or equal to a particular value. In particular, we show that the distortion-transmission function is a piecewise linear, convex, and decreasing function. We also give an explicit characterization of each vertex of the piecewise linear function. The results are illustrated using an example of a birth-death Markov chain.

Consider a communication system in which a transmitter observes n independent Markov sources and has to jointly quantize them in real-time for a single receiver. Although the model is a special case of real-time quantization of Markov sources, a direct application of the results of real-time quantization is infeasible due to computational complexity. We restrict attention to a encoding-decoding strategies having a specific structure, and identify a dynamic program to find the best strategies with that structure. This dynamic program has uncountable state space. For the special case when all source alphabets are equal to each other and to the quantization alphabet, we reduce the dynamic program to one with a countable state space. We then present a finite-state approximation of this dynamic programming. The feasibility of the approach is shown by means of examples.

We consider the optimal design of a sensing system in which a sensor can choose how and when to communicate to an estimator. The optimal choice of transmission and estimation policies is made difficult by the fact that the sensor and the estimator may use their entire history of observations. Traditionally, Markov decision theory is used to analyze such multi-stage decision problems. But, Markov decision theory assumes a single decision maker-an assumption that is not satisfied in an active sensing system that has two decision makers with different information. In this paper, we use the approach of Nayyar et al (2011) to investigate the system as a dynamic team. Using a series of structural results, we show that the optimal policy is easy to implement. We also obtain a dynamic programming decomposition to find optimal sensing and estimation policies.

Variable length communication over a compound channel with feedback is considered. Traditionally, capacity of a compound channel without feedback is defined as the maximum rate that is determined before the start of communication such that communication is reliable. This traditional definition is pessimistic. In the presence of feedback, an opportunistic definition is given. Capacity is defined as the maximum rate that is determined at the end of communication such that communication is reliable. Thus, the transmission rate can adapt to the realized channel. Under this definition, feedback communication over a compound channel is conceptually similar to multiterminal communication. Transmission rate is a vector rather than a scalar; channel capacity is a region rather than a scalar; error exponent is a region rather than a scalar. In this paper, variable length communication over a compound channel with feedback is formulated, its opportunistic capacity region is characterized, and lower bounds for its error exponent region are provided.

Capacity of a compound channel without feedback is defined in a pessimistic manner as the maximum rate determined before the start of communication such that communication is reliable. In the presence of feedback, the transmission rate can adapt to the channel chosen by nature. Thus, capacity can be defined in an opportunistic manner as the maximum rate determined at the end of communication such that communication is reliable. Under this definition, transmission rate and error exponents are regions rather than scalars. In this paper, variable length communication over a compound channel with feedback is formulated, its opportunistic capacity region is characterized, and lower bounds for its error exponent region are provided.

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.

A graphical model for sequential teams is presented. This model is easy to understand, and at the same time, is general enough to model any finite horizon sequential team with finite valued system variables and unconstrained decision rules. The model can also be represented as a directed acyclic factor graph. This representation makes it easier to visualize and understand the functional dependencies between different system variables. It also helps in identifying data that is irrelevant for a decision maker to take an optimal decision. Such irrelevant data can be identified using algorithms from graphical models. Thus, the structural properties of optimal decision makers in this model for a sequential team can be identified in an automated manner using the directed acyclic factor graph representation of the sequential team.

Optimal design of sequential real-time communication of a Markov source over a noisy channel is investigated. In such a system, the delay between the source output and its reconstruction at the receiver should equal a fixed prespecified amount. An optimal communication strategy must minimize the total expected symbol-by-symbol distortion between the source output and its reconstruction. Design techniques or performance bounds for such real-time communication systems are unknown. In this paper a systematic methodology, based on the concepts of information structures and information states, to search for an optimal real-time communication strategy is presented. This methodology trades off complexity in communication length (linear in contrast to doubly exponential) with complexity in alphabet sizes (doubly exponential in contrast to exponential). As the communication length is usually order of magnitudes bigger than the alphabet sizes, the proposed methodology simplifies the search for an optimal communication strategy. In spite of this simplification, the resultant optimality equations cannot be solved efficiently using existing algorithmic techniques. The main idea is to formulate a zero-delay communication problem as a dynamic team with nonclassical information structure. Then, an appropriate choice of information states converts the dynamic team problem into a centralized stochastic control problem in function space. Thereafter, Markov decision theory is used to derive nested optimality equations for choosing an optimal design. For infinite horizon problems, these optimality equations give rise to a fixed point functional equation. Communication systems with fixed finite delay constraint, a higher-order Markov source, and channels with memory are treated in the same manner after an appropriate expansion of the state space. Thus, this paper presents a comprehensive methodology to study different variations of real-time communication.

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.

A real-time communication system with noisy feedback is considered. The system consists of a Markov source, forward and backward discrete memoryless channels, and a receiver with limited memory. The receiver can send messages to the encoder over the backward noisy channel. The encoding at the encoder and the decoding, the feedback, and the memory update at the receiver must be done in real-time. A distortion metric that does not tolerate delays is given. The objective is to design an optimal real-time communication strategy, i.e., design optimal real-time encoding, decoding, feedback, and memory update strategies to minimize a total expected distortion over a finite horizon. This problem is formulated as a decentralized stochastic optimization problem and a methodology for its sequential decomposition is presented. This results in a set of nested optimality equations that can be used to sequentially determine optimal communication strategies. The methodology exponentially simplifies the search for determining an optimal real-time communication strategy.

We consider zero-delay or fixed finite-delay joint source channel coding of Markov sources using finite memory encoder and decoder. The objective is to choose designs that minimize expected total distortion over a finite horizon, expected discounted distortion over an infinite horizon and average distortion per unit time over an infinite horizon. The above problem is a dynamic team with non-classical information structure. We develop a sequential decomposition for this problem. The main contribution of this paper is to provide a systematic methodology for determination of optimal joint source-channel encoding-decoding strategies for zero-delay or fixed finite-delay point-to-point communication with limited memory

Simultaneous down-conversion of multiple band-pass signals is desirable for a number of wireless applications. Bandpass sampling technique can be used for this purpose, but it is difficult to implement and has several drawbacks. In this paper we propose a novel front-end technique to directly down-convert multiple frequency- division multiplexed (FDM) signals separated by certain minimum frequency. A special downconversion function is derived to achieve simultaneous downconversion of the received signals. The technique requires simpler bandpass filters and the ADC has a baseband input as compared to bandpass sampling, which imposes strict requirements on bandpass filters and requires an ADC which can handle RF inputs. The performance of the method has been evaluated by simulating a BPSK receiver employing this technique.