Deep Neural Networks (DNNs) have demonstrated exceptional performance in diverse tasks. However, deploying DNNs on resource-constrained devices presents challenges due to energy consumption and delay overheads. To mitigate these issues, early-exit DNNs (EE-DNNs) incorporate exit branches within intermediate layers to enable early inferences. These branches estimate prediction confidence and employ a fixed threshold to determine early termination. Nonetheless, fixed thresholds yield suboptimal performance in dynamic contexts, where context refers to distortions caused by environmental conditions, in image classification, or variations in input distribution due to concept drift, in NLP. In this article, we introduce Upper Confidence Bound in EE-DNNs (UCBEE), an online algorithm that dynamically adjusts early exit thresholds based on context. UCBEE leverages confidence levels at intermediate layers and learns without the need for true labels. Through extensive experiments in image classification and NLP, we demonstrate that UCBEE achieves logarithmic regret, converging after just a few thousand observations across multiple contexts. We evaluate UCBEE for image classification and text mining. In the latter, we show that UCBEE can reduce cumulative regret and lower latency by approximately 10%–20% without compromising accuracy when compared to fixed threshold alternatives. Our findings highlight UCBEE as an effective method for enhancing EE-DNN efficiency.

Deep Neural Networks (DNNs) are widely used to solve a growing number of tasks, such as image classification. However, their deployment at resource-constrained devices still poses challenges related to energy consumption and delay over-heads. Early-Exit DNNs (EE-DNNs) address the challenges by adding side branches through their architecture. Under an edge-cloud co-inference, if the confidence at a side branch is larger than a fixed confidence threshold, the inference is performed completely at the edge device, saving computation for more difficult observations. Otherwise, the edge device offloads the inference task to the cloud, incurring overhead. Despite its success, EE-DNNs for image classification have to cope with distorted images. The baseline distortion level depends on the environmental context, e.g., time of the day, lighting, and weather conditions. To cope with varying distortion, we propose Adaptive Early-Exit in Deep Neural Networks (AdaEE), a novel algorithm to dynamically adjust the confidence threshold based on context, leveraging the Upper Confidence Bound (UCB) for that matter. AdaEE provably achieves logarithmic regret under mild conditions. We experimentally verify that 1) convergence occurs after collecting a few thousand observations for images with different distortion levels and overhead values, and 2) AdaEE obtains a lower cumulative regret when compared against alternatives using the Caltech-256 dataset subject to varying distortion.

Dynamic resource allocation mechanism is an essential building block in contemporary cloud computing environment, enabling the support of the large variability of incoming requests from an enormous number of applications utilizing such cloud infrastructure. In this article, we devise a dynamic resource allocation mechanism that optimizes the application’s profit under the set of costs and revenues while maintaining performance constraints. Specifically, we devise a decision-maker (DM) agent which formulates the joint admission control, scaling and load balancing problem as a stochastic process solvable by Markov decision process (MDP) which provides the optimal policy. Accordingly, at each time instance, the DM can determine based on the system’s current state, on the set of requirements and on the set of costs, whether to add or release a VM (scale-out or scale-in, respectively), whether to admit or reject an upcoming task and if admitting it, which VM to allocate it to. We explore the value function structure and provide insights with respect to the optimal policies produced from it. To address scalability issues of the detailed MDP solution we provide an alternative solution by abstract MDP which consolidates multiple system states into a single abstract state, hence can cope with much larger systems at the expense of slight performance degradation. To demonstrate the feasibility of the suggested scheme, we designed and implemented it, alongside with two traditional auto-scalers, on the Amazon Web Services (AWS) infrastructure. We ran numerous MATLAB simulations and AWS-based experiments which provided insights and demonstrated superiority against the traditional policies we compared with.

In this work, we study the optimal configuration of the physical layer in wireless networks by means of Semi-Markov Decision Process (SMDP) modeling. In particular, assume the physical layer is characterized by a set of potential operating points, with each point corresponding to a rate and reliability pair; for example, these pairs might be obtained through a now-standard diversity-multiplexing tradeoff characterization. Given the current network state (e.g., buffer occupancies), a Decision Maker (DM) needs to dynamically decide which operating point to use. The SMDP problem formulation allows us to choose from these points. A solution to the SMDP problem is an optimal selection of operating points, which is expressed by a decision rule as a function of the number of packets in the source's finite queue, the channel state, and the size of the packet to be transmitted. We derive a general solution to the SMDP which covers various model configurations, packet size distributions and channel dynamics. For the specific case of exponential transmission times, we analytically prove the optimal policy has a threshold structure. Numerical results validate this finding, as well as depict muti-threshold policies for time varying channels such as the Gilbert-Elliott channel.

Consider a transmission scheme with a single transmitter and multiple receivers over a faulty broadcast channel. For each receiver, the transmitter has a unique infinite stream of packets, and its goal is to deliver them at the highest throughput possible. While such multiple-unicast models are unsolved in general, several network coding-based schemes were suggested. In such schemes, the transmitter can either send an uncoded packet, or a coded packet which is the function of a few packets. The packets sent can be received by the designated receiver (with some probability) or heard and stored by other receivers. Two functional modes are considered; the first presumes that the storage time is unlimited, while in the second one it is limited by the given time to expire (TTE) parameter. We model the transmission process as an infinite-horizon Markov decision process (MDP). Since the large state space renders exact solutions computationally impractical, we introduce policy-restricted and induced MDPs with significantly reduced state space, and prove that with proper reward function they have equal optimal value function (hence equal optimal throughput). We then derive a reinforcement learning algorithm, which learns the optimal policy for the induced MDP. This optimal strategy of the induced MDP, once applied to the policy of the restricted one, significantly improves over uncoded schemes. Next, we enhance the algorithm by means of analysis of the structural properties of the resulting cost functional. We demonstrate that our method scales well in the number of users, and automatically adapts to the packet loss rates, unknown in advance. In addition, the performance is compared to the recent bound by Wang, which assumes much stronger coding (e.g., intrasession and buffering of coded packets), yet is shown to be comparable