Abstract
Edge Computing (EC) offers a superior user experience by positioning cloud resources in close proximity to end users. The challenge of allocating edge resources efficiently while maximizing profit for the EC platform remains a sophisticated problem, especially with the added complexity of the online arrival of resource requests. To address this challenge, we propose to cast the problem as a multi-armed bandit problem and develop two novel online pricing mechanisms, the Kullback-Leibler Upper Confidence Bound (KL-UCB) algorithm and the Min-Max Optimal algorithm (MOSS), for heterogeneous edge resource allocation. These mechanisms operate in real-time and do not require prior knowledge of demand distribution. Numerical results show the advantages of the proposed mechanisms compared to several benchmark schemes derived from traditional bandit algorithms, including Epsilon-Greedy, basic UCB, and Thompson Sampling.
Introduction
Edge Computing (EC) places processing power close to users to support low-latency applications like AR/VR and autonomous driving. However, managing an EC platform is a complex balancing act involving geographically dispersed Edge Nodes (ENs) with limited capacity and diverse hardware configurations.
The core challenge is online pricing. In real-world scenarios, resource requests arrive sequentially, and the platform typically lacks prior knowledge of the "demand distribution"—the private valuation each buyer has for a specific resource. Traditional pricing models often assume a static environment or require historical data that may not be available. This research addresses the need for a "distribution-free" mechanism that can learn the optimal price dynamically, accounting for the fact that a buyer’s preference depends on both the VM's power and its physical location.
The Multi-Armed Bandit Framework
To solve the online pricing problem, we model it as a Multi-Armed Bandit (MAB). In this setup, the platform "pulls an arm" by choosing a price vector from a set of $K$ discrete pricing options. It then observes the "reward" (the revenue from the sale) and uses that feedback to improve future pricing decisions. Unlike many previous works, this model allows buyers to purchase multiple products (different VM types at different locations) simultaneously.
We propose two specific algorithms to manage the exploration-exploitation trade-off:
- Kullback-Leibler Upper Confidence Bound (KL-UCB): A sophisticated version of the standard UCB algorithm that uses KL divergence to create tighter, more mathematically rigorous confidence bounds on expected rewards. This allows for more efficient exploration of the pricing space.
- Min-Max Optimal Strategy (MOSS): Designed to minimize worst-case regret, MOSS uses a unique UCB calculation specifically tuned for stochastic bandits to achieve a distribution-free regret bound.
Performance Evaluation
We evaluated the algorithms through numerical simulations involving 3 Edge Nodes, 9 distinct products, and 100,000 sequential buyers. To test robustness, buyer valuations were generated using Uniform, Gaussian, and Exponential distributions.
As shown in Figure 1, both KL-UCB and MOSS significantly outperformed traditional benchmarks like Epsilon-Greedy (EG) and basic UCB in terms of cumulative reward and regret. KL-UCB generally exhibited the lowest regret across the tested distributions.
The Thompson Sampling Trap
A key insight from our experiments is the failure of Thompson Sampling (TS) in specific scenarios. While TS is often considered a "gold standard" in MAB problems, it performed poorly when buyer valuations followed an exponential distribution.
As illustrated in Figure 3, the heavy tails of the exponential distribution make it difficult for TS to converge on the optimal price arm. In contrast, KL-UCB and MOSS remained robust, maintaining high cumulative rewards and accurately identifying the optimal pricing arms.
Computational Trade-offs
While KL-UCB provides superior accuracy, it is computationally heavier because it requires solving an optimization problem at every step. Our results indicate that MOSS is significantly faster (e.g., ~12 seconds vs ~101 seconds for 500 arms), making it more suitable for high-dimensional pricing spaces where real-time speed is critical.
Conclusion and Future Work
Our proposed KL-UCB and MOSS mechanisms provide effective, distribution-free solutions for online edge resource pricing. They successfully balance the need to explore different price points with the goal of maximizing immediate revenue. Future research will explore continuous price spaces, integrate complex inventory management constraints, and consider competitive scenarios involving multiple edge providers.
Summary updated