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.

We consider the discrete time infinite horizon average reward restless markovian bandit (RMAB) problem. We propose a model predictive control based non-stationary policy with a rolling computational horizon $\tau$. At each time-slot, this policy solves a $\tau$ horizon linear program whose first control value is kept as a control for the RMAB. Our solution requires minimal assumptions and quantifies the loss in optimality in terms of $\tau$ and the number of arms, $N$. We show that its sub-optimality gap is $O(1/\sqrt{N})$ in general, and $\exp(-\Omega(N))$ under a local-stability condition. Our proof is based on a framework from dynamic control known as dissipativity. Our solution is easy to implement and performs very well in practice when compared to the state of the art. Further, both our solution and our proof methodology can easily be generalized to more general constrained MDP settings and should thus be of great interest to the burgeoning RMAB community.

We address the challenge of zeroth-order online convex optimization where the objective function's gradient exhibits sparsity, indicating that only a small number of dimensions possess non-zero gradients. Our aim is to leverage this sparsity to obtain useful estimates of the objective function's gradient even when the only information available is a limited number of function samples. Our motivation stems from the optimization of large-scale queueing networks that process time-sensitive jobs. Here, a job must be processed by potentially many queues in sequence to produce an output, and the service time at any queue is a function of the resources allocated to that queue. Since resources are costly, the end-to-end latency for jobs must be balanced with the overall cost of the resources used. While the number of queues is substantial, the latency function primarily reacts to resource changes in only a few, rendering the gradient sparse. We tackle this problem by introducing the Compressive Online Gradient Optimization framework which allows compressive sensing methods previously applied to stochastic optimization to achieve regret bounds with an optimal dependence on the time horizon without the full problem dimension appearing in the bound. For specific algorithms, we reduce the samples required per gradient estimate to scale with the gradient's sparsity factor rather than its full dimensionality. Numerical simulations and real-world microservices benchmarks demonstrate CONGO's superiority over gradient descent approaches that do not account for sparsity.

With the proliferation of short form high quality video content, it has become increasing important to find light weight and efficient edge caching algorithms that can quickly adapt to changing trends. In this context we study an online caching problem where a set of users are connected to a set of caches. The users request files from these caches over a time horizon. These requests arrive sequentially, the sequence of requests are divided into tasks that have a certain degree of similarity. This similarity is leveraged so that we may learn the best policy for a new task using a very small number of sequential requests. We characterize the task averaged regret incurred in this setting, showing an improvement of$D/D^{*}$where D is the diameter of the set of cache configurations and$D^{*}$is a measure of task similarity. We provide the same theoretical guarantees under both a distributed and smoothed setting. Further, we validate our algorithm on trace based data as well as on synthetic data sets. In the trace based data sets we do not assume any inherent task structure or estimate of$D^{*}$. These simulations show not only fast adaptation to new incoming tasks but also improved performance in highly non-stationary request settings.

We study the optimal control of multiple video streams over a wireless downlink from a base-transceiver-station (BTS)/access point to N end-devices (EDs). The BTS sends video packets to each ED under a joint transmission energy constraint, the EDs choose when to play out the received packets, and the collective goal is to provide a high Quality-of-Experience (QoE) to the clients/end-users. All EDs send feedback about their states and actions to the BTS which reaches it after a fixed deterministic delay. We analyze this team problem with delayed feedback as a cooperative Multi-Agent Constrained Partially Observable Markov Decision Process (MA-C-POMDP).First, using a recently established strong duality result for MAC-POMDPs, the original problem is decomposed into N independent unconstrained transmitter-receiver (two-agent) problems— all sharing a Lagrange multiplier (that also needs to be optimized for optimal control). Thereafter, the common information (CI) approach and the formalism of approximate information states (AISs) are used to guide the design of a neural-network based architecture for learning-based multi-agent control in a single unconstrained transmitter-receiver problem. Finally, simulations on a single transmitter-receiver pair with a stylized QoE model are performed to highlight the advantage of delay-aware two-agent coordination over the transmitter choosing both transmission and play-out actions (perceiving the delayed state of the receiver as its current state).

We consider an ultra-dense wireless network with$N$channels and$M = N$devices. Messages with fresh information are generated at each device according to a random process and need to be transmitted to an access point. The value of a message decreases as it ages, so each device searches for an idle channel to transmit the message as soon as it can. However, each channel probing is associated with a fixed cost (energy), so a device needs to adapt its probing rate based on the “age” of the message. At each device, the design of the optimal probing strategy can be formulated as an infinite horizon Markov Decision Process (MDP) where the devices compete with each other to find idle channels. While it is natural to view the system as a Bayesian game, it is often intractable to analyze such a system. Thus, we use the Mean Field Game (MFG) approach to analyze the system in a large-system regime, where the number of devices is very large, to understand the structure of the problem and to find efficient probing strategies. We present an analysis based on the MFG perspective. We begin by characterizing the space of valid policies and use this to show the existence of a Mean Field Nash Equilibrium (MFNE) in a constrained set for any general increasing cost functions with diminishing rewards. Further we provide an algorithm for computing the equilibrium for any given device, and the corresponding age-dependent channel probing policy.

We consider an ultra-dense wireless network with N channels and M = N devices. Messages with fresh information are generated at each device according to a random process and need to be transmitted to an access point. The value of a message decreases as it ages, so each device searches for an idle channel to transmit the message as soon as it can. However, each channel probing is associated with a fixed cost (energy), so a device needs to adapt its probing rate based on the "age" of the message. At each device, the design of the optimal probing strategy can be formulated as an infinite horizon Markov Decision Process (MDP) where the devices compete with each other to find idle channels. While it is natural to view the system as a Bayesian game, it is often intractable to analyze such a system. Thus, we use the Mean Field Game (MFG) approach to analyze the system in a large-system regime, where the number of devices is very large, to understand the structure of the problem and to find efficient probing strategies. We present an analysis based on the MFG perspective. We begin by characterizing the space of valid policies and use this to show the existence of a Mean Field Nash Equilibrium (MFNE) in a constrained set for any general increasing cost functions with diminishing rewards. Further we provide an algorithm for computing the equilibrium for any given device, and the corresponding age-dependent channel probing policy.

This report analyzes the performance of distributed Medium Access Control (MAC) protocols in ultra-dense multichannel wireless networks, where$N$frequency bands (or channels) are shared by$M=mN$devices, and devices make decisions to probe and then transmit over available frequency bands. While such a system can be formulated as an$M$-player Bayesian game, it is often infeasible to compute the Nash equilibria of a large-scale system due tothe curse of dimensionality. In this report, we exploit the Mean Field Game (MFG) approach and analyze the system in the large population regime ($N$tends to$\infty $and$m$is a constant). We consider a distributed and low complexity MAC protocol where each device probes$d/k$channels by following an exponential clock which ticks with rate$k$when it has a message to transmit, and optimizes the probing strategy to balance throughput and probing cost. We present a comprehensive analysis from the MFG perspective, including the existence and uniqueness of and convergence to the Mean Field Nash Equilibrium and the price of anarchy with respect to the global optimal solution. Our analysis shows that the price of anarchy is at most one half, but is close to zero when the traffic load or the probing cost is low. Our numerical results confirm our analysis and show that the MFNE is a good approximation of the$M$-player system. Further, this report demonstrates the novelty of MFG analysis, which can be used to study other distributed MAC protocols in ultra-dense wireless networks.

This paper analyzes the performance of distributed Medium Access Control (MAC) protocols in ultra-dense multichannel wireless networks, where N frequency bands (or channels) are shared by M = mN devices, and devices make decisions to probe and then transmit over available frequency bands. While such a system can be formulated as an M-player Bayesian game, it is often infeasible to compute the Nash equilibria of a large-scale system due to the curse of dimensionality. In this paper, we exploit the Mean Field Game (MFG) approach and analyze the system in the large population regime (N tends to ∞ and m is a constant). We consider a distributed and low complexity MAC protocol where each device probes d/k channels by following an exponential clock which ticks with rate k when it has a message to transmit, and optimizes the probing strategy to balance throughput and probing cost. We present a comprehensive analysis from the MFG perspective, including the existence and uniqueness of the Mean Field Nash Equilibrium (MFNE), convergence to the MFNE, and the price of anarchy with respect to the global optimal solution. Our analysis shows that the price of anarchy is at most one half, but is close to zero when the traffic load or the probing cost is low. Our numerical results confirm our analysis and show that the MFNE is a good approximation of the M-player system. Besides showing the efficiency of the considered MAC for emerging applications in ultra-dense multichannel wireless networks, this paper demonstrates the novelty of MFG analysis, which can be used to study other distributed MAC protocols in ultra-dense wireless networks.