Efficiently managing data transmission across unreliable communication channels for diverse sources has attracted much attention due to its great practicability in the Internet of Things systems. Despite its significance in real-time wireless systems, ensuring stringent freshness requirements for each information source remains an understudied challenge, especially in scenarios demanding heterogeneous quality-of-service guarantees. In this paper, we study a scheduling problem of maximizing the accumulated information subject to different Age of Information (AoI) requirements for heterogeneous information sources. To that end, we first present a global optimal transmission scheduling policy when the source statistics are known a priori. Then, as this information is unknown, we formulate the problem as an AoI-constrained Multi-Armed bandit and propose an efficient learning algorithm, named O-SRS. Furthermore, we theoretically show that O-SRS achieves$O(\sqrt{T \log T})$regret while meeting the AoI requirement of each source. Finally, comprehensive simulations are conducted to demonstrate our theoretical results.

Evolution of the 5G network introduces much higher QoS standards and energy saving objectives, which requires a more refined and smoothed online control method in many scenarios. To address this challenge, we study the online decision problem with switching costs where the agent incurs both a convex hitting cost and an additional switching cost of changing decisions, i.e., Smoothed Online Convex Optimization (SOCO). While there have been a wide variety of online algorithms designed, their theoretical performance relies on certain assumptions about loss functions, e.g., linearity and smoothness, predictability, or prior knowledge of regularity measures of environment. This paper addresses this limitation by developing a universal algorithm IOMD-SOCO that applies to general convex loss functions without predictions. We show that IOMD-SOCO achieves an order-optimal, universal dynamic regret bound. We also propose its parameter-free versions, i.e., without requiring the prior knowledge of path length of the comparator sequence, and achieve the same-order regret bound. We are the first to provide dynamic regret bounds for SOCO with general convex loss functions via parameter-free algorithms. Our numerical experiments show that IOMD-SOCO indeed achieves a substantial performance improvement. We also discuss potential applications of SOCO in communication networks.

We consider a decentralized multi-player multi-armed bandit (MP-MAB) problem where players cannot observe the actions and rewards of other players and no explicit communication or coordination between players is possible. Prior studies mostly focus on maximizing the sum of rewards of the players over time. However, the total reward maximization learning may lead to imbalanced reward among players, leading to poor Quality of Service (QoS) for some players. In contrast, our objective is to let each player n achieve a predetermined expected average reward over time, i.e., achieving a predetermined level of QoS. We develop a novel decentralized MP-MAB algorithm to accomplish this objective by leveraging the methodology of randomized matching. We prove that our decentralized algorithm can ensure that all players have an O(1) QoS regret. We also reveal an analog between our MP-MAB model and the online wireless queuing systems, which builds a connection between QoS in MP-MAB learning and stability in queuing theory.

The design of effective online caching policies is an increasingly important problem for content distribution networks, online recommender systems, and edge computing services, etc. Exiting literature usually tackles this problem through the lens of optimistic online learning and aims to achieve sublinear regret. In this paper, we focus on a non-trivial extension of classic online caching problem inspired by operational requirements of real-world systems including switching costs and long-term constraints. To tackle the challenges of switching costs and operational long-term constraints in the online caching, we introduce the Block-structured Follow-the-Regularized-Leader (B-FTRL) caching policy. Our approach incorporates a block structure that divides time into blocks to minimize caching switching costs. The theoretical analysis shows that B-FTRL achieves a utility regret bound of $O\left( {{T^{\frac{{2a - b + 1}}{{1 + a}}}} + {T^{\frac{b}{{1 + a}}}}} \right)$ and switching costs bound of $O\left( {{T^{\frac{1}{{1 + a}}}}} \right)$, where a and b are tunable algorithm parameters. By carefully selecting the values of a and b, we are able to limit the total regret to O(T2/3) while satisfying the operational long-term constraints in expectation. Additionally, we provide high-probability constraint violation bounds of $O\left( {\sqrt T } \right)$. The performance of the proposed algorithm is evaluated with detailed trace-driven numerical tests.

The multi-armed bandits (MAB) framework is widely used for sequential decision-making under uncertainty, finding applications in various domains, including computer and communication networks. To address the increasing complexity of real-world systems and their operational requirements, researchers have proposed and studied various extensions to the basic MAB framework. In this paper, we focus on an adversarial MAB problem inspired by real-world systems with combinatorial semi-bandit arms, switching costs, and anytime cumulative arm selection constraints. To tackle this challenging problem, we introduce the Block-structured Follow-the-Regularized-Leader (B-FTRL) algorithm. Our approach employs a hybrid Tsallis-Shannon entropy regularizer in arm selection and incorporates a block structure that divides time into blocks to minimize arm switching costs. The theoretical analysis shows that B-FTRL achieves a reward regret bound of $O\left( {{T^{\frac{{2a - b + 1}}{{1 + a}}}} + {T^{\frac{b}{{1 + a}}}}} \right)$ and a switching regret bound of $O\left( {{T^{\frac{1}{{1 + a}}}}} \right)$, where a and b are tunable algorithm parameters. By carefully selecting the values of a and b, we are able to limit the total regret to O(T2/3) while satisfying the arm selection constraints in expectation. This outperforms the state-of-the-art regret bound of O(T3/4) and expected constraint violation bound o(1), which are derived in less challenging stochastic reward environments. Additionally, we provide a high-probability constraint violation bound of $O(\sqrt T )$. To validate the effectiveness of the proposed BFTRL algorithm, numerical results are presented to demonstrate its superiority in comparison to other existing methods.

The problem of scheduling packets from multiple sources over unreliable channels has attracted much attention due to its great practicability in the Internet of things systems. Most previous work focuses on the throughput/energy consumption/operational cost optimization or the setting that the channel information is known a priori. In this paper, we consider a more generic setting to this problem where packets from different sources have different values, and each heterogeneous source has a distinct Quality of Service (QoS) requirement. The information about packet value and channel reliability is unknown in advance, and the controller schedules sources over time to maximize its collected packet values while providing a QoS guarantee for each source. For the stationary case where packet values are independent and identically distributed (i.i.d.), we propose an efficient learning policy based on linear-programming (LP) methodology. Our proof shows that it meets the QoS constraint of each source and only incurs a logarithmic regret. In the special case that the channel reliability is known a priori, our algorithm can further guarantee a bounded regret. Furthermore, in the case of non-stationary packet values, we apply the sliding window technique to our LP-based algorithm and prove that it still guarantees a sublinear regret while meeting each source’s QoS requirement. Finally, we provide numerical simulations to support our theoretical results.

We consider the task scheduling scenario where the controller activates one from K task types at each time. Each task induces a random completion time, and a reward is obtained only after the task is completed. The statistics of the completion time and the reward distributions of all task types are unknown to the controller. The controller needs to learn to schedule tasks to maximize the accumulated reward within a given time horizon T. Motivated by the practical scenarios, we require the designed policy to satisfy a system throughput constraint. In addition, we introduce the interruption mechanism to terminate ongoing tasks that last longer than certain deadlines. To address this scheduling problem, we model it as an online learning problem with deadline and throughput constraints. Then, we characterize the optimal offline policy and develop efficient online learning algorithms based on the Lyapunov method. We prove that our online learning algorithm achieves an$O(\sqrt {T})$regret and zero constraint violation. We also conduct simulations to evaluate the performance of our developed learning algorithms.

We study the caching problem from an online learning point-of-view, i.e., no model assumptions and prior knowledge for the file request sequence. Our goal is to design an efficient online caching policy with minimal regret, i.e., minimizing the total number of cache miss with respect to the best static configuration in hindsight. Previous studies, such as Follow-The-Perturbed-Leader (FTPL) and Follow-The-Regularized-Leader (FTRL) caching policies, have provided some near-optimal results, but their theoretical performance guarantees only valid for the regime wherein all arrival requests could be seen by the cache, which is not the case in some practical scenarios. Hence our work closes this gap by considering the partial-observation regime wherein only requests for currently cached files are seen by the cache, which is more challenging and has not been studied before. We propose an online caching policy integrating the FTPL with a popularity estimation procedure called Geometric Resampling (GR), which is the first no-regret policy in this regime (achieve sublinear regret guarantee). Moreover, in the partial-observation regime, we also consider the caching problem with additional operational requirements of real-world systems, i.e., long-term constraints, and proposed a modified version of FTRL combining with GR to address this challenge setting. The theoretical analysis shows that this caching policy is able to achieve no-regret guarantee while satisfying the operational long-term constraints in expectation. Finally, we conduct numerical experiments to validate the theoretical guarantees of our proposed caching policies.

Online resource allocation problem with budget constraints has a wide range of applications in network science and operation research. In this problem, the decision maker needs to make actions that consume resources to accumulate rewards. Contrary to prior work, we introduce a non-linear and non-separable regularizer to this problem that acts on the total resource consumption. The motivation for introducing the regularizer is allowing the decision maker to tradeoff the reward maximization and metrics optimization such as load-balancing and fairness that appears frequently in practical needs. Our goal is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer without violating resource budget constraints. We develop a primal-dual-type online algorithm for this problem in the online learning setting and confirm its no-regret guarantee and zero constraint violations for stochastic i.i.d. input models. Furthermore, the general convex resource consumption functions allow our model to be more applicable. Numerical experiments are conducted to demonstrate the theoretical guarantee of our algorithm.

We consider the task scheduling scenario where the controller activates one from K task types at each time. Each task induces a random completion time, and a reward is obtained only after the task is completed. The statistics of the completion time and the reward distributions of all task types are unknown to the controller. The controller needs to learn to schedule tasks to maximize the accumulated reward within a given time horizon T . Motivated by the practical scenarios, we require the designed policy to satisfy a system throughput constraint. In addition, we introduce the interruption mechanism to terminate ongoing tasks that last longer than certain deadlines. To address this scheduling problem, we model it as an online learning problem with deadline and throughput constraints. Then, we characterize the optimal offline policy and develop efficient online learning algorithms based on the Lyapunov method. We prove that our online learning algorithm achieves an $O(\sqrt T )$ regret and zero constraint violations. We also conduct simulations to evaluate the performance of our developed learning algorithms.

We consider the caching problem in an online learning perspective, i.e., no model assumptions and prior knowledge for the file request sequence. Our goal is to design an efficient on-line caching policy with minimal regret, i.e, minimizing the total number of cache-miss with respect to the best static configuration in hindsight. Previous studies such as Follow-The-Perturbed-Leader (FTPL) caching policy, have provided some near-optimal results, but their theoretical performance guarantees only valid for the regime wherein all arrival requests could be seen by the cache, which is not the case in some practical scenarios like caching at cellular base station, content dissemination via DNS, etc. Hence our work study the partial-feedback regime wherein only requests for currently cached files are seen by the cache, which is more challenging and has not been studied before in the online learning perspective. We propose an online caching policy combining the FTPL with a novel popularity estimation procedure called Geometric Resampling (GR), and show that it yields the first sublinear regret guarantee in this regime. We also conduct numerical experiments to validate the theoretical guarantees of our caching policy.

This paper proposes and studies for the first time the problem of combinatorial multi-armed bandits with linear long-term constraints. Our model generalizes and unifies several prominent lines of work, including bandits with fairness constraints, bandits with knapsacks (BwK), etc. We propose an upper-confidence bound LP-style algorithm for this problem, called UCB-LP, and prove that it achieves a logarithmic problem-dependent regret bound and zero constraint violations in expectation. In the special case of fairness constraints, we further provide a sharper constant regret bound for UCB-LP. Our regret bounds outperform the existing literature on BwK and bandits with fairness constraints simultaneously. We also develop another low-complexity version of UCB-LP and show that it yields $\tilde{O}(\sqrt{T})$ problem-independent regret and zero constraint violations with high-probability. Finally, we conduct numerical experiments to validate our theoretical results.

In this paper, we study the problem of online convex optimization with switching costs (SOCO) that appears in diverse scenarios including power management, video streaming, resource allocation, etc. SOCO refers to online decision problems when the agent incurs both hitting cost and an additional switching cost of changing decisions. We adopt the universal dynamic regret as the performance metric, and consider the case when loss functions are unknown when making decisions. Previous results rely on the assumptions on loss function, e.g., linearity and smoothness, or prior knowledge of regularity measures, e.g., path length of the comparator sequence. In this paper, we propose an algorithm IOMD-SOCO that applies to general convex loss function, and show that the algorithm achieves an order-optimal universal dynamic regret bound. We also propose its parameter-free versions, i.e., without requiring the prior knowledge of path length of the comparator sequence, and achieve the same-order regret bound. We are the first to provide dynamic regret bounds for SOCO with general convex loss functions via parameter-free algorithm. Our numerical experiments show that IOMD-SOCO indeed achieves a substantial performance improvement.

Network address translation (NAT) is a basic functionality in cloud gateways. With the increasing traffic volume and number of flows introduced by the cloud tenants, the NAT gateway needs to be implemented on a cluster of servers. We propose to scale up the gateway servers, which could reduce the number of servers so as to reduce the capital expense and operation expense. We design HyperNAT, which leverages smartNICs to improve the server's processing capacity. In HyperNAT, the NAT functionality is distributed on multiple NICs, and the flow space is divided and assigned accordingly. HyperNAT overcomes the challenge that the packets in two directions of one connection need to be processed by the same NAT rule (named two-direction consistency, TDC) by cloning the rule to both data paths of the two directions. Our implementation and evaluation of HyperNAT show that HyperNAT could scale up cloud gateway effectively with low overhead.