Abstract
In infrastructureless wireless networks, such as ad-hoc and device-to-device (D2D) systems, the absence of a central controller necessitates decentralized optimization strategies. This paper explores a framework for joint channel selection and power control using a multi-player adversarial multi-armed bandit (MP-MAB) approach. By employing "no-regret" learning strategies—specifically NR-BEWAS and NR-BFPLS—selfish nodes can achieve performance levels comparable to a centralized optimal controller. Crucially, the framework enables nodes to converge to a correlated equilibrium without inter-node communication or prior knowledge of the network topology, even in highly dynamic, adversarial environments.
Introduction
Modern wireless communication is increasingly moving toward infrastructureless architectures where transmitters must autonomously decide on frequency channels and power levels. This environment presents three significant challenges: nodes are inherently selfish, aiming to maximize their own throughput; they possess limited information regarding fading gains or the actions of interferers; and the environment is often adversarial, with signal quality fluctuating unpredictably rather than following a steady statistical distribution.
Traditional solutions often rely on heavy communication overhead or assume stationary environments. This research addresses these limitations by modeling the interaction as a game where "blind" nodes must coordinate implicitly. The objective is to minimize "regret"—the difference between a node's actual performance and the performance of the best fixed strategy available in hindsight.
Methodology: Multi-Player Multi-Armed Bandits
The problem is formulated as a Multi-Player Multi-Armed Bandit (MP-MAB) game. Each "arm" available to a player represents a unique combination of a frequency channel and a transmit power level. To navigate the exploration-exploitation trade-off in an adversarial setting, the authors propose two primary no-regret strategies:
- NR-BEWAS (No-Regret Bandit Exponential-Based Weighted Average Strategy): Derived from the Exp3 algorithm, this method assigns selection probabilities to actions based on exponentially weighted past rewards. This ensures that better-performing arms are favored while maintaining sufficient exploration to adapt to environmental changes.
- NR-BFPLS (No-Regret Bandit Follow the Perturbed Leader Strategy): In this approach, nodes track the accumulated regret for each action and add a random perturbation (noise). By choosing the action that appears best under this perturbed history, nodes avoid being exploited by adversarial patterns in the network.
Achieving Correlated Equilibrium
A central technical contribution of this work is the conversion of external regret (comparison to the single best action) into internal regret (comparison to a strategy that swaps one action for another). The authors demonstrate that by minimizing internal regret, the decentralized network is mathematically guaranteed to settle into a correlated equilibrium. This allows for sophisticated coordination without any explicit exchange of information between nodes.
Performance Evaluation
The proposed algorithms were evaluated through extensive numerical simulations across various scales:
- Small-Scale Scenarios: A 2-user network with 2 channels and 2 power levels was used to visualize strategy evolution.
- Large-Scale Scenarios: A 5-user network with 3 channels and 2 power levels (6 possible actions per user) tested scalability against benchmarks like $\epsilon$-greedy and standard greedy approaches.
- Channel Modeling: The simulations incorporated Rayleigh fading and path loss, with rewards calculated based on the Shannon capacity formula minus a penalty for power consumption.
Key Results
- Convergence to Centralized Optimal: Both NR-BEWAS and NR-BFPLS achieved average rewards that converged to the performance of a centralized controller with global knowledge.
- Sublinear Regret: The authors proved that regret grows sublinearly (e.g., $O(n^{2/3})$ or $O(n^{1/2})$), indicating that the average regret per time step vanishes as the system operates over time.
- Algorithmic Trade-offs: NR-BFPLS demonstrated faster convergence than NR-BEWAS but required higher local computational power due to the complexity of calculating selection probabilities via integration.
- Robustness: The proposed methods significantly outperformed standard greedy algorithms, which frequently failed to adapt to the interference patterns or became trapped in sub-optimal states.
Discussion and Future Work
The framework demonstrates that coordination in complex wireless environments is possible through local observation alone. The use of adversarial bandit theory ensures the system is robust against unpredictable network changes that typically disrupt stochastic models. Furthermore, the application of deliberate noise (perturbation) in NR-BFPLS highlights a counter-intuitive path to long-term stability in decentralized systems.
However, limitations remain. The computational overhead for NR-BFPLS may become a bottleneck as the number of channels and power levels increases. Additionally, while the framework scales well to small-to-medium networks, its application in massive IoT or MIMO scenarios—where hundreds of nodes interact—requires further investigation into the polynomial growth of regret relative to the number of players. Future research will also focus on defining the precise set of correlated equilibria for general time-varying cases where stationary characterizations do not apply.
Summary updated