Constrained combinatorial contextual bandits have emerged as trending tools in intelligent systems and networks to model reward and cost signals under combinatorial decision-making. On one hand, both signals are complex functions of the context, e.g., in federated learning, training loss (negative reward) and energy consumption (cost) are nonlinear functions of edge devices’ system conditions (context). On the other hand, there are cumulative constraints on costs, e.g., the accumulated energy consumption should be budgeted by energy resources. Besides, real-time systems often require such constraints to be guaranteed anytime or in each round, e.g., ensuring anytime fairness for task assignment to maintain the credibility of crowdsourcing platforms for workers. This bandit setting presents significant challenges, including modeling complex rewards/costs, satisfying anytime cumulative constraints, and balancing exploration and exploitation. Therefore, we propose a primal-dual algorithm (Neural-PD) with neural network-based estimations for rewards/costs and virtual queue-based optimization for constraints. Besides, we provide theoretical guarantees regarding the behavior of neural network training within the primal-dual framework and the dynamic neural tangent kernel (NTK) of the neural networks during online learning. By integrating NTK theory and Lyapunov-drift techniques, we prove Neural-PD achieves a sharp regret bound and a zero constraint violation. We also show Neural-PD outperforms existing algorithms with extensive experiments on both synthetic and real-world datasets.

Meta-learning has earned its wide popularity to handle a family of similar tasks (e.g., classification of pets and wildlife) with elaborately trained meta-knowledge (e.g., shared network architecture and neural network parameter initialization). In this paper, we focus on the distributed training of meta-knowledge via server-device collaboration at the edge (i.e., distributed meta-learning). Notably, its practical implementation often runs into concerns like 1) time-varying unknown wireless dynamics (e.g., transmission latency); 2) device-side fair device involvement in distributed training; 3) server-side resource efficiency. To address such concerns, 1) we employ online learning to estimate the unknown dynamics and further exploit social ties among device users to accelerate online learning; 2) we utilize online control techniques to handle long-term fairness and resource constraints. By characterizing inter-user social ties as a social graph, we study distributed meta-learning from the perspective of constrained graphical bandits. Therefore, we propose a SoCial-awarE meta-kNowledge dispaTch (SCENT) algorithm by effectively integrating graphical bandit learning and online control. Besides a sublinear regret (i.e., loss of performance), SCENT also guarantees a well-trained meta-knowledge under within-budget resource consumption and fair device involvement. We conduct simulations to justify the outperformance of SCENT compared with baselines.

Constrained combinatorial contextual bandits have emerged as trending tools in intelligent systems and networks to model reward and cost signals under combinatorial decision-making. On one hand, both signals are complex functions of the context, e.g., in federated learning, training loss (negative reward) and energy consumption (cost) are nonlinear functions of edge devices’ system conditions (context). On the other hand, there are cumulative constraints on costs, e.g., the accumulated energy consumption should be budgeted by energy resources. Besides, real-time systems often require such constraints to be guaranteed anytime or in each round, e.g., ensuring anytime fairness for task assignment to maintain the credibility of crowdsourcing platforms for workers. This setting imposes a challenge on how to simultaneously achieve reward maximization while subjecting to anytime cumulative constraints. To address such challenge, we propose a primal-dual algorithm (Neural-PD) whose primal component adopts multi-layer perceptrons to estimate reward and cost functions, and its dual component estimates the Lagrange multiplier with the virtual queue. By integrating neural tangent kernel theory and Lyapunov-drift techniques, we prove Neural-PD achieves a sharp regret bound and a zero constraint violation. We also show Neural-PD outperforms existing algorithms with extensive experiments on both synthetic and real-world datasets.

The flourished edge intelligence has motivated the execution of machine learning tasks at the network edge. In this paper, we focus on distributing training, one of the core tasks, that is carried out by an edge server of limited communication capacity and multiple end devices. In distributed training, the key issue for the edge server is how to dynamically select a proper subset of end devices to periodically participate in the training. Such a dynamic end device selection problem is hindered by concerns like 1) unknown system dynamics, e.g., transmission latencies; 2) limited energy resources on end devices; and 3) unbalanced and non-IID data distribution over end devices. Therefore, the core challenge lies in the coordination of online learning and online control to fulfill both efficient learning of unknown statistics and guarantees of within-budget energy consumption and fairness selection. To address the above challenge, we first characterize the social ties among users of end devices as a social graph and then formulate the dynamic end device selection problem from the perspective of constrained graphical bandits. Under the formulation, we propose GRIND to effectively integrate graphical bandit learning methods with Lyapunov-drift techniques. The theoretical superiority of GRIND is not only 1) the achieved sub-linear round-averaged regret with satisfied long-term constraints but also 2) the characterization of graph structure with the independence number. Extensive simulations also verify the effectiveness of GRIND in terms of both latency reduction and long-term constraint satisfaction.

For systems that are based on network function virtualization (NFV), it remains a key challenge to conduct effective service chain composition with the lowest request latency and the minimum network congestion. In such an NFV system, users are usually non-cooperative, i.e., they compete with each other to optimize their own benefits. However, existing solutions often ignore such non-cooperative behaviors of users. What is more, they may fall short in the face of unexpected resource failures such as breakdown of virtual machines and loss of connections to users. In this article, we formulate the service chain composition problem with resource failures in NFV systems as a non-cooperative game, and show that such a game is a weighted potential game, aiming to search for the optimal Nash equilibrium (NE). By adopting Markov approximation techniques, we devise a distributed scheme called MH-SCCA, which achieves a provably near-optimal NE and adapts to resource failures in a timely manner. For comparison, we also propose two baseline schemes (DRL-SCCA and MCTS-SCCA) for centralized service chain composition that are based on deep reinforcement learning (DRL) and Monte Carlo tree search (MCTS) techniques, respectively. Our simulation results demonstrate the effectiveness of the three proposed schemes in terms of both latency reduction and congestion mitigation, as well as the adaptivity of MH-SCCA when faced with resource failures.

For NFV systems, the key design space includes the function chaining for network requests and the resource scheduling for servers. The problem is challenging since NFV systems usually require multiple (often conflicting) design objectives and the computational efficiency of real-time decision making with limited information. Furthermore, the benefits of predictive scheduling to NFV systems still remain unexplored. In this article, we propose POSCARS, an efficient predictive and online service chaining and resource scheduling scheme that achieves tunable trade-offs among various system metrics with stability guarantee. Through a careful choice of granularity in system modeling, we acquire a better understanding of the trade-offs in our design space. By a non-trivial transformation, we decouple the complex optimization problem into a series of online sub-problems to achieve the optimality with only limited information. By employing randomized load balancing techniques, we propose three variants of POSCARS to reduce the overheads of decision making. Theoretical analysis and simulations show that POSCARS and its variants require only mild-value of future information to achieve near-optimal system cost with an ultra-low request response time.

In multitiered fog computing systems, to accelerate the processing of computation-intensive tasks for real-time Internet of Things (IoT) applications, resource-limited IoT devices can offload part of their workloads to nearby fog nodes, whereafter such workloads may be offloaded to upper-tier fog nodes with greater computation capacities. Such hierarchical offloading, though promising to shorten processing latencies, may also induce excessive power consumptions and latencies for wireless transmissions. With the temporal variation of various system dynamics, such a tradeoff makes it rather challenging to conduct effective and online offloading decision making. Meanwhile, the fundamental benefits of predictive offloading to fog computing systems still remain unexplored. In this article, we focus on the problem of dynamic offloading and resource allocation with traffic prediction in multitiered fog computing systems. By formulating the problem as a stochastic network optimization problem, we aim to minimize the time-average power consumptions with stability guarantee for all queues in the system. We exploit unique problem structures and propose predictive offloading and resource allocation (PORA), an efficient and distributed PORA scheme for multitiered fog computing systems. Our theoretical analysis and simulation results show that PORA incurs near-optimal power consumptions with queue stability guarantee. Furthermore, PORA requires only mild value of predictive information to achieve a notable latency reduction, even with the prediction errors.

For software-defined networking (SDN) systems, to enhance the scalability and reliability of control plane, existing solutions adopt either multi-controller design with static switch-controller association, or static control devolution by delegating certain request processing back to switches. Such solutions can fall short in face of temporal variations of request traffics, incurring considerable local computation costs on switches and their communication costs to controllers. So far, it still remains an open problem to develop a joint online scheme that conducts dynamic switch-controller association and dynamic control devolution. In addition, the fundamental benefits of predictive scheduling to SDN systems still remain unexplored. In this paper, we identify the non-trivial trade-off in such a joint design and formulate a stochastic network optimization problem which aims to minimize time-averaged total system costs and ensure long-term queue stability. By exploiting the unique problem structure, we devise a predictive online switch-controller association and control devolution (POSCAD) scheme, which solves the problem through a series of online distributed decision making. Theoretical analysis shows that without prediction, POSCAD can achieve near-optimal total system costs a tunable trade-off for queue stability. With prediction, POSCAD can achieve even better performance with shorter latencies. We conduct extensive simulations to evaluate POSCAD. Notably, with mild-value of future information, POSCAD incurs a significant reduction in request latencies, even when faced with prediction errors.

A key challenge in the design space of fog computing systems is online task scheduling, i.e., to allocate multiple types of resources to pending tasks that are constantly generated from end devices. It is challenging because of the online, intensive, and time-varying nature of task arrival, the varieties in the amounts and durations of task resource demands, as well as the unattainability of such priori information due to the online nature of task arrivals. To handle such uncertainties, an online task scheduler design with flexibility to process sequences of task arrivals with variable lengths is highly demanded. Existing works have adopted deep reinforcement learning (DRL) techniques to develop online task schedulers in a data-driven fashion by constructing them as neural networks and training using empirical data. However, hindered by the intrinsic restriction of the underlying neural network design, such schedulers often suffer from poor flexibility that may induce resource under- utilization, or overly fine-grained control that induces considerable overheads. In this paper, we address the above challenges by integrating pointer network architecture with the scheduler design, and proposing Neural Task Scheduling (NTS), an online flexible task scheduling scheme which effectively reduces average task slowdown to facilitate best quality-of-service. Simulation results show that NTS consistently outperforms state-of-the-art schemes under different settings.

For NFV systems, the key design space includes the function chaining for network requests and resource scheduling for servers. The problem is challenging since NFV systems usually require multiple (often conflicting) design objectives and the computational efficiency of decision making with limited information. Besides, the limits and benefits of predictive scheduling to NFV systems still remain unexplored. In this paper, we propose POSCARS, an efficient, distributed, and online algorithm that achieves a tunable trade-off between various system metrics with stability guarantee, while exploiting the power of predictive scheduling. Using randomized load balancing techniques, we propose three variants of POSCARS to further reduce sampling overheads. Theoretical analysis and trace-driven simulations show that POSCARS and its variants require only mild-value of future information to achieve a near- optimal average system cost while effectively shortening the average request response time.

Network functions virtualization (NFV) initiates a revolution of network service (NS) delivery by forming each NS as a chain of virtual network functions across commodity servers. However, it still remains a key challenge in NFV to decide the chains that induce short latency and low congestion, a.k.a. service chain composition problem. Existing works mainly resort to centralized solutions that require full knowledge of the network state to coordinate different users' traffic and NSs, overlooking privacy issues and the non-cooperative interactions among users. Moreover, handling the possible failures due to user/resource unavailability makes the problem even more challenging. By modeling the service chain composition problem with respect to both user and resource failures as a noncooperative game, we formulate the problem as searching the Nash Equilibrium (NE) with the optimal system performances. By exploiting the unique problem structure, we show that the game is a weighted potential game. We propose DISCCA, a distributed and low-complexity algorithm that guides the system towards the NE with short latency and low congestion, through decision making by individual users with local information. Results from extensive simulations show that DISCCA effectively achieves near-optimal system performances within mild-value of iterations, even in the presence of failures.

Fog computing is a promising paradigm that enables Internet-of-Things (IoT) applications with ultra-low latency and intensive computation. However, it is challenging to make efficient online decisions under varying system dynamics and intertwined power-latency tradeoffs. Moreover, the fundamental limits and benefits of predictive offloading in fog computing systems still remain unknown. In this paper, we study the problem of dynamic workload offloading and resource allocation in multi-tiered fog computing systems. By developing a fine-grained queue model and formulate a stochastic network optimization problem, we propose PORA, an efficient scheme that exploits predictive information to solve the problem. Results from our theoretical analysis and simulations show that PORA achieves a near-optimal power consumption with low latencies. Furthermore, PORA effectively reduces latencies with only mild-value of predictive information and it's robust against prediction errors.

In software-defined networking (SDN) systems, the scalability and reliability of the control plane still remain as major concerns. Existing solutions adopt either multi-controller designs or control devolution back to the data plane. The former requires a flexible yet efficient switch-controller association mechanism to adapt to workload changes and potential failures, while the latter demands timely decision making with low overheads. The integrate design for both is even more challenging. Meanwhile, the dramatic advancement in machine learning techniques has boosted the practice of predictive scheduling to improve the responsiveness in various systems. Nonetheless, so far little work has been conducted for SDN systems. In this paper, we study the joint problem of dynamic switch-controller association and control devolution, while investigating the benefits of predictive scheduling in SDN systems. We propose POSCAD, an efficient, online, and distributed scheme that exploits predictive future information to minimize the total system cost and the average request response time with queueing stability guarantee. Theoretical analysis and trace-driven simulation results show that POSCAD requires only mild-value of future information to achieve a near-optimal system cost and near-zero average request response time. Further, POSCAD is robust against mis-prediction to reduce the average request response time.

In fog computing systems, one key challenge is online task scheduling, i.e., to decide the resource allocation for tasks that are continuously generated from end devices. The design is challenging because of various uncertainties manifested in fog computing systems; e.g., tasks' resource demands remain unknown before their actual arrivals. Recent works have applied deep reinforcement learning (DRL) techniques to conduct online task scheduling and improve various objectives. However, they overlook the multi-resource fairness for different tasks, which is key to achieving fair resource sharing among tasks but in general non-trivial to achieve. Thus it is still an open problem to design an online task scheduling scheme with multi-resource fairness. In this paper, we address the above challenges. Particularly, by leveraging DRL techniques and adopting the idea of dominant resource fairness (DRF), we propose FairTS, an online task scheduling scheme that learns directly from experience to effectively shorten average task slowdown while ensuring multi-resource fairness among tasks. Simulation results show that FairTS outperforms state- of-the-art schemes with an ultra-low task slowdown and better resource fairness.

In software-defined networking (SDN), as data plane scale expands, scalability and reliability of the control plane have become major concerns. To mitigate such concerns, two kinds of solutions have been proposed separately. One is multi-controller architecture, i.e., a logically centralized control plane with physically distributed controllers. The other is control devolution, i.e., delegating control of some flows back to switches. Most of existing solutions adopt either static switch-controller association or static devolution, which may not adapt well to the traffic variation, leading to high communication costs between switches and controller, and high computation costs of switches. In this paper, we propose a novel scheme to jointly consider both solutions, i.e., we dynamically associate switches with controllers and dynamically devolve control of flows to switches. Our scheme is an efficient online algorithm that does not need the statistics of traffic flows. By adjusting some parameter V, we can make a trade-off between costs and queue backlogs. Theoretical analysis and extensive simulations show that our scheme yields much lower costs and latency compared to static schemes, and balanced loads among controllers.