🤖 machine learning

A Comparative Analysis on the Performance of Upper Confidence Bound Algorithms in Adaptive Deep Neural Networks

This paper introduces and evaluates four advanced Upper Confidence Bound strategies (UCB-V, UCB-Tuned, UCB-Bayes, and UCB-BwK) within Adaptive Deep Neural Networks to optimize the trade-offs between accuracy, energy consumption, and latency in edge computing, demonstrating that UCB-V and UCB-Tuned achieve superior performance on the Pareto Frontiers.

Original authors: Grigorios Papanikolaou, Ioannis Kontopoulos, Konstantinos Tserpes

Published 2026-04-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Grigorios Papanikolaou, Ioannis Kontopoulos, Konstantinos Tserpes

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a busy restaurant kitchen (your computer) that needs to serve thousands of dishes (data) every day. You have a team of chefs with different skill levels, from a quick prep cook to a master chef.

The Problem: The "One-Size-Fits-All" Kitchen
Traditionally, every single order, no matter how simple, goes all the way to the master chef. Even if a customer just ordered a plain toast, the kitchen wastes time and energy sending it through the entire complex cooking process. In the world of Artificial Intelligence, this is like running a massive Deep Neural Network for every single image, even simple ones. This uses too much battery (energy) and takes too long (latency), which is a big problem for devices like smartphones or sensors that run on limited power.

The Solution: The "Early Exit" Strategy
The paper introduces a smarter way called Adaptive Deep Neural Networks (ADNNs). Think of this as adding "taste testers" at different stages of the kitchen.

If the prep cook is 100% sure the toast is perfect, they can stop there and serve it immediately.
If they are unsure, they pass it to the next chef.
If the master chef is still unsure, they keep going until the very end.

This is called an "Early Exit." The goal is to stop as soon as you are confident enough, saving time and energy.

The Challenge: How to Decide When to Stop?
The tricky part is setting the rule for "when to stop."

If you stop too early, you might serve a burnt toast (low accuracy).
If you wait too long, you waste energy on a simple task (high latency).

Previously, researchers used a simple rulebook called UCB1 to decide when to stop. It's like a manager who says, "Let's try the quick exit first, but if we fail too often, we'll try the next one." It works okay, but it's a bit rigid.

The Paper's Innovation: A Better Rulebook
The authors of this paper asked: "What if we had smarter managers with different personalities?" They tested four new "managers" (algorithms) to see which one makes the best decisions for stopping early:

UCB-V (The Variance Watcher): This manager pays attention to how consistent the results are. If a chef has been very consistent (low variance), this manager trusts them quickly. If results are shaky (high variance), they keep testing longer.
UCB-Tuned (The Conservative Tuner): Similar to the Variance Watcher but adds a safety cap. If things get too unpredictable, this manager slows down and becomes more careful, preventing the kitchen from making reckless decisions.
UCB-Bayes (The Bayesian Expert): This manager uses a "gut feeling" based on past experience (mathematical priors). They are very good at learning the right rule quickly, but they are also very slow to think because they do a lot of complex mental math before making a move.
UCB-BwK (The Cost Counter): This manager looks at the "price" of every decision. They don't just look at how good the food is; they calculate exactly how much energy it cost to get there, trying to find the perfect balance between quality and cost.

The Experiment
The researchers tested these managers on two types of kitchens (neural networks): ResNet (a standard, reliable kitchen) and MobileViT (a newer, more efficient kitchen). They fed them thousands of images (from the CIFAR datasets) and measured:

Accuracy: How many dishes were served correctly?
Energy: How much battery was used?
Latency: How long did it take to serve the dish?

The Results

The Winners: UCB-V and UCB-Tuned were the best overall. They found the "sweet spot" where the kitchen saved the most energy and time without serving bad food. They dominated the "Pareto Frontier," which is a fancy way of saying they offered the best possible trade-offs between speed/energy and quality.
The Fast Learner: UCB-Bayes learned the best rules the fastest (lowest "regret"), meaning it figured out the right strategy quickly. However, because it does so much complex math in its head, it actually slowed down the kitchen, making it less useful for real-time devices.
The Slow Learners: The old standard (UCB1) and the cost-counter (UCB-BwK) were slower to learn and didn't perform as well as the variance-aware managers.

The Bottom Line
The paper proves that you don't need to use the same simple rule for every situation. By choosing the right "manager" (algorithm) for your specific device and task, you can make AI systems that are much faster and more energy-efficient. Specifically, for most edge devices, the UCB-V and UCB-Tuned strategies are the best tools to balance speed, battery life, and accuracy.

1. Problem Statement

Edge computing environments face strict constraints regarding energy consumption, latency, and computational resources. While Deep Neural Networks (DNNs) are powerful, their static inference processes often waste resources by processing all inputs through the full network depth, regardless of input difficulty.

Adaptive Deep Neural Networks (ADNNs), specifically Early-Exit DNNs (EEDNNs), address this by allowing the model to "exit" early if a prediction is made with high confidence at a shallow layer. However, determining the optimal confidence threshold for exiting is a critical challenge:

Static thresholds are inefficient because they do not adapt to varying input difficulties or resource constraints.
Current Dynamic Approaches primarily rely on the UCB1 (Upper Confidence Bound 1) algorithm within a Multi-Armed Bandit (MAB) framework. While UCB1 is simple, it ignores reward variance, cost awareness, and Bayesian uncertainty, potentially leading to suboptimal trade-offs between accuracy, energy, and latency.

The paper posits that different UCB variants possess distinct exploration-exploitation strategies that could yield superior performance in specific edge scenarios, yet this has not been systematically compared.

2. Methodology

The authors propose a comparative framework where the MAB agent dynamically selects the optimal confidence threshold for early exiting.

A. The MAB Framework

Arms: Each "arm" represents a discrete confidence threshold.
Reward Function: The reward is calculated based on a trade-off between prediction confidence, reliability, and computational cost:
$\text{reward} = C_{\text{EEDNN}} \times (1 - C_{\text{Gating}}) - \lambda \times \text{cost}$
- $C_{\text{EEDNN}}$ : Confidence from the EEDNN.
- $C_{\text{Gating}}$ : Reliability score from a lightweight gating network (lower is better).
- $\text{cost}$ : The index of the exit point (higher index = more layers = higher cost).
- $\lambda$ : A balancing factor for risk control.

B. Proposed UCB Variants

The study introduces four UCB variants into the EEDNN context, replacing the standard UCB1:

UCB-V: Incorporates empirical variance ( $\sigma^2$ ) into the exploration term. It is "variance-aware," exploring high-variance arms more aggressively while committing faster to stable, low-variance arms.
UCB-Tuned: Similar to UCB-V but uses a capped variance value ( $\tilde{V}$ ) to prevent overconfidence in early stages. It adopts a conservative strategy if variance exceeds 0.25.
UCB-Bayes: Uses Bayesian uncertainty (Normal-Inverse-Gamma priors) instead of frequentist statistics. It maintains a posterior distribution over the mean and variance of rewards, updating beliefs as data arrives.
UCB-BwK (Bandits with Knapsacks/Cost): Explicitly accounts for the cost of pulling an arm during the selection process. It optimizes the ratio of mean reward to mean cost ( $\mu/c$ ), rather than just maximizing reward.

3. Key Contributions

Novel Integration: First application of UCB-V, UCB-Tuned, UCB-Bayes, and UCB-BwK within Early-Exit DNNs for dynamic threshold selection.
Comprehensive Comparative Study: A systematic evaluation of these algorithms against the standard UCB1, analyzing trade-offs between accuracy, energy consumption, and latency.
Empirical Insights: Demonstration that the "best" algorithm depends on the specific constraints (e.g., variance-aware algorithms excel in energy/latency, while Bayesian methods excel in convergence speed).
Sub-linear Regret Proof: Empirical validation that all proposed strategies achieve sub-linear cumulative regret, a theoretical requirement for effective MAB performance.

4. Experimental Setup & Results

Architectures: ResNet18, ResNet34, ResNet50, and MobileViT (CNN-Transformer hybrid).
Datasets: CIFAR-10, CIFAR-100, and CIFAR-10.1 (to test distribution shift).
Metrics: Accuracy (%), Energy (kWh via CodeCarbon), Inference Time (Latency), and Cumulative Regret.

Key Findings:

Pareto Dominance (Accuracy vs. Energy/Latency):
- UCB-V and UCB-Tuned consistently dominate the Pareto frontiers. Their ability to leverage reward variance allows them to waste fewer samples on sub-optimal thresholds, leading to better energy and latency efficiency.
- UCB-BwK performs well on MobileViT architectures where reward variance is less pronounced, as it explicitly optimizes the reward-to-cost ratio.
Convergence Speed (Regret):
- UCB-Bayes converges the fastest regarding cumulative regret (reaching optimal thresholds in fewer steps).
- However, UCB-Bayes incurs higher computational overhead due to posterior calculations, making it less attractive for strict latency constraints compared to UCB-V/Tuned.
Model Architecture Impact:
- Larger models (ResNet34/50) benefit significantly more from dynamic thresholding than static approaches.
- MobileViT shows different variance characteristics, shifting the optimal algorithm preference toward UCB-BwK in some cases.
Regret Behavior: All strategies exhibit sub-linear cumulative regret, confirming their theoretical validity for online learning in inference. UCB1 and UCB-BwK generally showed higher average regret and slower convergence than the variance-aware and Bayesian variants.

5. Significance and Conclusion

This paper challenges the status quo of using only UCB1 for adaptive inference in edge AI. It demonstrates that variance-aware (UCB-V, UCB-Tuned) and Bayesian (UCB-Bayes) strategies offer distinct advantages:

For Edge Efficiency: UCB-V and UCB-Tuned are superior for minimizing energy and latency while maintaining accuracy.
For Rapid Adaptation: UCB-Bayes is ideal for scenarios requiring fast convergence to optimal policies, provided the computational overhead is acceptable.

Future Work: The authors plan to explore linear bandit variants (e.g., LinUCB) that utilize neural networks for context, though this may introduce higher inference costs.

Funding: The research was supported by the European Union's Horizon Europe research and innovation actions (Grant No 101215032).