The problem of constrained Markov game has recently attracted interests in the study of multi-agent reinforcement learning (MARL). The existing literature has focused on safe MARL problems where safety constraints are imposed for each agent individually. In this work, we consider Markov potential game (MPG) with a shared constraint, where the cost function with respect to the constraint depends on states and joint actions of all agents. We adopt a primal-dual framework to tackle the problem and establish the Slater condition to ensure the strong duality. Moreover, we propose our primal-dual learning algorithm for learning approximate Nash equilibrium in MPG with shared constraint. Thanks to the novel design of the dual update, we provide asymptotic convergence on the weighted output policy. Specifically, we prove that both the value function gap and the constraint violation of the output policy converge at the rate O(epsilon+1/sqrt(T)), where epsilon is the accuracy level of the primal update, and T is the number of iterations. We further show that the weighted output policy outperforms the existing uniformly chosen policy.

The problem of two-player zero-sum Markov games has recently attracted increasing interests in theoretical studies of multi-agent reinforcement learning (RL). In particular, for finite-horizon episodic Markov decision processes (MDPs), it has been shown that model-based algorithms can find an $\epsilon$-optimal Nash Equilibrium (NE) with the sample complexity of $O(H^3SAB/\epsilon^2)$, which is optimal in the dependence of the horizon $H$ and the number of states $S$ (where $A$ and $B$ denote the number of actions of the two players, respectively). However, none of the existing model-free algorithms can achieve such an optimality. In this work, we propose a model-free stage-based algorithm and show that it achieves the same sample complexity as the best model-based algorithm, and hence for the first time demonstrate that model-free algorithms can enjoy the same optimality in the $H$ dependence as model-based algorithms. The main improvement of the dependency on $H$ arises by leveraging the popular variance reduction technique based on the reference-advantage decomposition previously used only for single-agent RL. However, such a technique relies on a critical monotonicity property of the value function, which does not hold in Markov games due to the update of the policy via the coarse correlated equilibrium (CCE) oracle. Thus, to extend such a technique to Markov games, our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions whose value difference is the smallest in the history in order to achieve the desired improvement in the sample efficiency.

Function approximation has experienced significant success in the field of reinforcement learning (RL). Despite a handful of progress on developing theory for Nonstationary RL with function approximation under structural assumptions, existing work for nonstationary RL with general function approximation is still limited. In this work, we propose a UCB-type of algorithm LSVI-Nonstationary following the popular least-square-value-iteration (LSVI) framework. LSVI-Nonstationary features the restart mechanism and a new design of bonus term to handle nonstationarity, and performs no worse than the existing confidence-set based algorithm SW-OPEA in [1], which has been shown to outperform the existing algorithms for nonstationary linear and tabular MDPs in the small variation budget setting.

We study offline multitask representation learning in reinforcement learning (RL), where a learner is provided with an offline dataset from different tasks that share a common representation and is asked to learn the shared representation. We theoretically investigate offline multitask low-rank RL, and propose a new algorithm called MORL for offline multitask representation learning. Furthermore, we examine downstream RL in reward-free, offline and online scenarios, where a new task is introduced to the agent that shares the same representation as the upstream offline tasks. Our theoretical results demonstrate the benefits of using the learned representation from the upstream offline task instead of directly learning the representation of the low-rank model.

General function approximation is a powerful tool to handle large state and action spaces in a broad range of reinforcement learning (RL) scenarios. However, theoretical understanding of non-stationary MDPs with general function approximation is still limited. In this paper, we make the first such an attempt. We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs, which subsumes majority of existing tractable RL problems in static MDPs as well as non-stationary MDPs. Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA, which features a sliding window mechanism and a new confidence set design for non-stationary MDPs. We then establish an upper bound on the dynamic regret for the proposed algorithm, and show that SW-OPEA is provably efficient as long as the variation budget is not significantly large. We further demonstrate via examples of non-stationary linear and tabular MDPs that our algorithm performs better in small variation budget scenario than the existing UCB-type algorithms. To the best of our knowledge, this is the first dynamic regret analysis in non-stationary MDPs with general function approximation.

As representation learning becomes a powerful technique to reduce sample complexity in reinforcement learning (RL) in practice, theoretical understanding of its advantage is still limited. In this paper, we theoretically characterize the benefit of representation learning under the low-rank Markov decision process (MDP) model. We first study multitask low-rank RL (as upstream training), where all tasks share a common representation, and propose a new multitask reward-free algorithm called REFUEL. REFUEL learns both the transition kernel and the near-optimal policy for each task, and outputs a well-learned representation for downstream tasks. Our result demonstrates that multitask representation learning is provably more sample-efficient than learning each task individually, as long as the total number of tasks is above a certain threshold. We then study the downstream RL in both online and offline settings, where the agent is assigned with a new task sharing the same representation as the upstream tasks. For both online and offline settings, we develop a sample-efficient algorithm, and show that it finds a near-optimal policy with the suboptimality gap bounded by the sum of the estimation error of the learned representation in upstream and a vanishing term as the number of downstream samples becomes large. Our downstream results of online and offline RL further capture the benefit of employing the learned representation from upstream as opposed to learning the representation of the low-rank model directly. To the best of our knowledge, this is the first theoretical study that characterizes the benefit of representation learning in exploration-based reward-free multitask RL for both upstream and downstream tasks.

In this paper, we consider a status updating system where updates are generated at a constant rate at$K$sources and sent to the corresponding recipients through a noise-free broadcast channel. We assume that perfect channel state information (CSI) is available at the transmitter before each transmission, and the transmitter is able to utilize the CSI to precode the updates. Our object is to design optimal precoding schemes to minimize the summed averageage of information(AoI) at the recipients. Under various assumptions on the size of each update$B$, the number of transmit antennas$M$, and the number of receive antennas$N$at each user, this paper identifies the corresponding age-optimal precoding and transmission scheduling strategies. Specifically, for the case when$N=1$, a round-robin based updating scheme is shown to be optimal. For the two-user systems with$N>B$or$M\notin [N:2N]$, framed updating schemes are proven to be optimal. For other cases in the two-user systems, a framed alternating updating scheme is proven to be 2-optimal.

Consider an energy harvesting (EH) sensor that continuously monitors a system and sends time-stamped status update to a destination. The sensor harvests energy from nature and uses it to power its updating operations. The destination keeps track of the system status through the successfully received updates. With the recently introduced information freshness metric “Age of Information” (AoI), our objective is to design optimal online status updating policy to minimize the long-term average AoI at the destination, subject to the energy causality constraint at the sensor. Due to the noisy channel between the sensor and the destination, each transmitted update may be erased with a fixed probability, and the AoI at the destination will be reset to zero only when an update is successfully received. We first consider status updating without feedback available to the sensor and show that the Best-effort Uniform updating (BU) policy is optimal in a broadly defined class of online policies. We then investigate status updating with perfect feedback to the sensor and prove similar optimality of the Best-effort Uniform updating with Retransmission (BUR) policy. In order to prove the optimality of the proposed policies, for each case, we first identify a lower bound on the long-term average AoI among a broad class of online policies, and then construct a sequence of virtual policies to approach the lower bound asymptotically. Since those virtual policies are sub-optimal to the original policy, the original policy is thus optimal.

In this paper, we consider a status updating system where updates are generated at a constant rate at K sources and sent to the corresponding recipients through a broadcast channel. We assume that perfect channel state information (CSI) is available at the transmitter before each transmission, and the additive noise is negligible at the receivers. Under various assumptions on the number of antennas at the transmitter and the size of updates, our object is to design precoding and transmission scheduling schemes for the minimization of the summed time-average Age of Information (AoI) at the recipients. We show that when the transmitter has a single antenna, precoding is unnecessary, and the optimal policy is to update each recipient in a greedy round-robin fashion. When the transmitter has multiple antennas, updating with round-robin precoding is age-optimal.

In this paper, we investigate the impact of coding on the Age of Information (AoI) in a two- user broadcast symbol erasure channel with feedback. We assume each update consists of K symbols and the source is able to broadcast one symbol in each time slot. Due to random channel noise, the intended symbol at each user will be erased according to an independent and identically distributed (i.i.d.) Bernoulli process. A user is able to successfully decode an update if it accumulates sufficient information and successfully decodes the K symbols of the update. Assuming perfect feedback information at the source right after the transmission of each symbol, our objective is to design an adaptive coding scheme to achieve small AoI at both users. We propose a novel coding scheme to judiciously combine symbols from different updates together, and analyze the AoI at both users. Compared with a baseline greedy scheme, the proposed adaptive coding scheme improves the AoI at the weak user by orders of magnitude without compromising the AoI at the strong user.

In this paper, we examine a status updating system where updates generated by the source are sent to the monitor through an erasure channel. We assume each update consists of k symbols and the symbol erasure in each time slot follows an independent and identically distributed (i.i.d.) Bernoulli process. We assume rateless coding scheme is adopted at the transmitter and an update can be successfully decoded if k coded symbols are received successfully. We assume perfect feedback available at the source, so that it knows whether a transmitted symbol has been erased instantly. Then, at the beginning of each time slot, the source has the choice to start transmitting a new update, or continue with the transmission of the previous update if it is not delivered yet. We adopt the metric “Age of Information” (AoI) to measure the freshness of information at the destination, where the AoI is defined as the age of the latest decoded update at the destination. Our objective is to design an optimal online transmission scheme to minimize the time-average AoI. The transmission decision is based on the instantaneous AoI, the age of the update being transmitted, as well as the number of successfully delivered symbols of the update. We formulate the problem as a Markov Decision Process (MDP) and identify the monotonic threshold structure of the optimal policy. Numerical results corroborate the structural properties of the optimal solution.

In this paper, we consider a status monitoring system where an energy harvesting sensor continuously sends time-stamped status updates to a destination. With a non-zero probability, each update will be corrupted by noise and result in an updating failure. The destination keeps track of the system status through the successfully delivered updates. We assume that there is a perfect feedback channel between the destination and the source, so that the source is aware of the updating failures once they occur. With the feedback information, our objective is to design the optimal online status updating policy to minimize the expected long-term average Age of Information (AoI) at the destination, subject to the energy causality constraint at the sensor. We propose a status updating policy called Best-effort Uniform updating with Retransmission (BUR), under which the source tries to equalize the delay between two successful updates as much as possible, and retransmits an update immediately if the previous transmission fails. We show that the BUR policy achieves the minimum expected long-term average AoI among a broad class of online policies.