Distributed Task Management in Fog Computing: A Socially Concave Bandit Game

• URL: http://arxiv.org/abs/2203.14572v2
• Date: Fri, 9 Jun 2023 15:15:14 GMT
• Title: Distributed Task Management in Fog Computing: A Socially Concave Bandit Game
• Authors: Xiaotong Cheng and Setareh Maghsudi
• Abstract summary: Fog computing leverages the task offloading capabilities at the network's edge to improve efficiency and enable swift responses to application demands. We formulate the distributed task allocation problem as a social-concave game with bandit feedback. We develop two no-regret online decision-making strategies.
• Score: 7.708904950194129
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fog computing leverages the task offloading capabilities at the network's edge to improve efficiency and enable swift responses to application demands. However, the design of task allocation strategies in a fog computing network is still challenging because of the heterogeneity of fog nodes and uncertainties in system dynamics. We formulate the distributed task allocation problem as a social-concave game with bandit feedback and show that the game has a unique Nash equilibrium, which is implementable using no-regret learning strategies (regret with sublinear growth). We then develop two no-regret online decision-making strategies. One strategy, namely bandit gradient ascent with momentum, is an online convex optimization algorithm with bandit feedback. The other strategy, Lipschitz bandit with initialization, is an EXP3 multi-armed bandit algorithm. We establish regret bounds for both strategies and analyze their convergence characteristics. Moreover, we compare the proposed strategies with an allocation strategy named learning with linear rewards. Theoretical- and numerical analysis shows the superior performance of the proposed strategies for efficient task allocation compared to the state-of-the-art methods.

Related papers

• Paths to Equilibrium in Games [6.812247730094933]
  We study sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning. Our analysis reveals a counterintuitive insight that reward deteriorating strategic updates are key to driving play to equilibrium along a satisficing path.
  arXiv  Detail & Related papers  (2024-03-26T19:58:39Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks. We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
  arXiv  Detail & Related papers  (2023-07-07T15:03:42Z)
• Towards Optimal Randomized Strategies in Adversarial Example Game [13.287949447721115]
  The vulnerability of deep neural network models to adversarial example attacks is a practical challenge in many artificial intelligence applications. We propose the first algorithm of its kind, called FRAT, which models the problem with a new infinite-dimensional continuous-time flow on probability distribution spaces. We prove that the continuous-time limit of FRAT converges to a mixed Nash equilibria in a zero-sum game formed by a defender and an attacker.
  arXiv  Detail & Related papers  (2023-06-29T07:29:23Z)
• Sampling-based Reactive Synthesis for Nondeterministic Hybrid Systems [20.0212772540119]
  This paper introduces a sampling-based strategy synthesis algorithm for nondeterministic hybrid systems. We model the evolution of the hybrid system as a two-player game, where the nondeterminism is an adversarial player. The aim is to synthesize a winning strategy -- a reactive (robust) strategy that guarantees the satisfaction of the goals under all possible moves of the adversarial player.
  arXiv  Detail & Related papers  (2023-04-14T00:45:16Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Mixed Strategies for Security Games with General Defending Requirements [37.02840909260615]
  The Stackelberg security game is played between a defender and an attacker, where the defender needs to allocate a limited amount of resources to multiple targets. We propose an efficient close-to-optimal Patching algorithm that computes mixed strategies that use only few pure strategies.
  arXiv  Detail & Related papers  (2022-04-26T08:56:39Z)
• Projective Ranking-based GNN Evasion Attacks [52.85890533994233]
  Graph neural networks (GNNs) offer promising learning methods for graph-related tasks. GNNs are at risk of adversarial attacks.
  arXiv  Detail & Related papers  (2022-02-25T21:52:09Z)
• Learning Generative Deception Strategies in Combinatorial Masking Games [27.2744631811653]
  One way deception can be employed is through obscuring, or masking, some of the information about how systems are configured. We present a novel game-theoretic model of the resulting defender-attacker interaction, where the defender chooses a subset of attributes to mask, while the attacker responds by choosing an exploit to execute. We present a novel highly scalable approach for approximately solving such games by representing the strategies of both players as neural networks.
  arXiv  Detail & Related papers  (2021-09-23T20:42:44Z)
• Online Adversarial Attacks [57.448101834579624]
  We formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases. We first rigorously analyze a deterministic variant of the online threat model. We then propose algoname, a simple yet practical algorithm yielding a provably better competitive ratio for $k=2$ over the current best single threshold algorithm.
  arXiv  Detail & Related papers  (2021-03-02T20:36:04Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  We study a novel variant of online finite-horizon Markov Decision Processes with adversarially changing loss functions and initially unknown dynamics. In each episode, the learner suffers the loss accumulated along the trajectory realized by the policy chosen for the episode, and observes aggregate bandit feedback. Our main result is a computationally efficient algorithm with $O(sqrtK)$ regret for this setting, where $K$ is the number of episodes.
  arXiv  Detail & Related papers  (2021-01-31T16:49:07Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  We provide the first universal and optimal reduction from contextual bandits to online regression. Our algorithm requires no distributional assumptions beyond realizability, and works even when contexts are chosen adversarially.
  arXiv  Detail & Related papers  (2020-02-12T11:33:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.