Global Bandits.

Area of Science:

• Machine Learning
• Artificial Intelligence
• Optimization

Background:

• Multiarmed bandits (MABs) are standard for sequential decision-making with independent arm rewards.
• Real-world problems often feature correlated arm rewards, where choosing one arm informs others.
• Existing MAB models do not adequately address these correlated reward structures.

Purpose of the Study:

• To introduce and analyze a novel class of models called global bandits (GB) for correlated reward scenarios.
• To develop and evaluate algorithms for sequential decision-making under correlated rewards.
• To demonstrate the practical benefits of the proposed GB model in dynamic pricing applications.

Main Methods:

• Proposed a global bandits (GB) model to capture correlations between arm rewards.
• Developed a greedy policy for GB with deterministic reward functions tied to a single parameter.
• Derived regret bounds, including parameter-dependent and parameter-independent sublinear bounds.
• Introduced a variant greedy policy for worst-case, parameter-dependent regret.

Main Results:

• The greedy policy guarantees bounded regret, selecting suboptimal arms finitely often with probability one.
• Achieved a sublinear regret bound independent of the true parameter, dependent on arm informativeness.
• Experimental results on dynamic pricing show significant performance gains over benchmarks.

Conclusions:

• Global bandits (GB) effectively model sequential decision problems with correlated rewards.
• The proposed greedy policies provide strong theoretical guarantees and practical advantages.
• GB algorithms offer substantial improvements in applications like dynamic pricing.