Push-Sum Distributed Online Optimization With Bandit Feedback.

Area of Science:

• Distributed Systems
• Optimization Theory
• Network Science

Background:

• Online convex optimization (OCO) is crucial for sequential decision-making in dynamic environments.
• Multiagent systems face challenges in decentralized learning due to communication constraints and partial feedback.
• Bandit feedback settings, where only the cost at the chosen action is revealed, complicate traditional OCO approaches.

Purpose of the Study:

• To develop a novel distributed online convex optimization algorithm for multiagent systems operating under time-varying, uniformly strongly connected directed graphs.
• To address the challenges of bandit feedback and limited information exchange between nodes.
• To achieve sublinear individual regret for each agent in the system.

Main Methods:

• The proposed algorithm integrates the push-sum scheme, relaxing the need for doubly stochastic weight matrices.
• It employs a one-point gradient estimator, requiring only the function value at a single point per iteration, not full gradient information.
• The algorithm is designed for Lipschitz continuous and strongly convex cost functions.

Main Results:

• The developed algorithm guarantees sublinear individual regret for every node in the multiagent system.
• The expected regret is shown to scale as O(T^(2/3) ln^(2/3)(T)), where T is the number of iterations.
• Simulations on a common numerical example validate the algorithm's performance.

Conclusions:

• The novel distributed online convex optimization algorithm effectively handles bandit feedback in multiagent systems.
• The algorithm's theoretical regret bounds and simulation results demonstrate its practical applicability and efficiency.
• This work contributes to advancing decentralized learning strategies in complex, dynamic network environments.