In a Hierarchical Inference (HI) system, an end device processes data samples using a local Deep Learning (DL) model. Only when the confidence of the local DL is less than a chosen threshold, it offloads the sample for remote DL inference on an edge server. By balancing the misclassifications and offloading costs, a HI system can improve accuracy and responsiveness and reduce bandwidth usage. To this end, prior work studied a HI learning problem for classification tasks, aiming to learn an optimal threshold on the confidence to minimize the cumulative costs. However, existing formulations considered (i) abstract offloading costs and (ii) assumed that the remote DL inference for an offloaded task is available by the end of each round. In contrast, considering that end devices are wirelessly connected to edge servers, we study a HI system with an offload queue where the offloading cost is implicitly modeled by the queue length. Also, we consider the practical setting, where the remote DL inference is obtained only after the task is served from the offload queue. For bounded but unknown arrival and service processes, we formulate the problem of average mismatch error minimization subject to queue stability. We propose a BOLD Hedge-Q policy based on Lyapunov optimization. The novelty of BOLD Hedge-Q lies in solving a delayed-feedback online learning problem — with sub-linear regret — that results from the Lyapunov drift-plus-penalty analysis. Given a penalty parameter V ≥ 1, we show that under BOLD Hedge-Q, the queue is upper bounded by V + λm, and the mismatch error is within an additive factor of O(1/V) from that of the optimal policy, where λm is the maximum number of arrivals in a round.

We consider a large-scale service marketplace with numerous servers that scale with the job arrival rate. Jobs arrive with private valuations representing their willingness to pay. In a centralized system, jobs are matched to available servers, and prices are set in a centralized manner to maximize revenue. We investigate whether similar scalability can be achieved in a distributed marketplace where jobs are randomly matched to servers, which set their own prices based on job valuations and system occupancy. Our results show that matching a job to a single randomly selected server leads to higher blocking, resulting in lower throughput and reduced revenue. We then examine matching jobs to two servers, which compete to provide service if unoccupied. We demonstrate the existence of a mean field equilibrium (MFE) in this setup, where servers strategically respond to competitors’ prices. We characterize the MFE and show that this two-server choice ensures lower blocking probabilities and higher system revenue. Our findings are validated through simulations illustrating a variety of operating scenarios.