Per-Round Knapsack-Constrained Linear Submodular Bandits.

Area of Science:

• Machine Learning
• Information Retrieval
• Optimization

Background:

• Linear submodular bandits are effective for diversification and feature-based exploration in information retrieval.
• Web applications like news recommendations and online advertising often face budget constraints.
• Existing methods may not adequately address diversification under strict budget limitations.

Purpose of the Study:

• To introduce and analyze the problem of diversification under a budget constraint in a bandit setting.
• To develop algorithms for per-round knapsack-constrained linear submodular bandits.
• To establish theoretical guarantees and evaluate practical performance.

Main Methods:

• Formulated the per-round knapsack-constrained linear submodular bandits problem.
• Defined an [Formula: see text]-approximation unit-cost regret.
• Proposed two greedy algorithms utilizing a modified UCB rule.
• Incorporated a modified lazy evaluation process for acceleration.

Main Results:

• Developed two greedy algorithms with proven regret bounds and computational complexities.
• Demonstrated that a modified lazy evaluation can accelerate algorithms without compromising theoretical guarantees.
• Experimental results validated the theoretical analyses.

Conclusions:

• The proposed algorithms effectively address diversification under budget constraints in linear submodular bandit settings.
• The theoretical framework and experimental validation provide a strong foundation for practical applications.
• This work advances the state-of-the-art in constrained bandit problems for recommender systems.