Linear submodular bandits with a knapsack constraint

Yu, B; Fang, M; Tao, D

Linear submodular bandits with a knapsack constraint

Yu, B Fang, M Tao, D

Permalink

Publication Type:: Conference Proceeding
Citation:: 30th AAAI Conference on Artificial Intelligence, AAAI 2016, 2016, pp. 1380 - 1386
Issue Date:: 2016-01-01

Closed Access

	Filename	Description	Size
	LinearSub.pdf	Published version	684.35 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Yu, B	en_US
dc.contributor.author	Fang, M	en_US
dc.contributor.author	Tao, D https://orcid.org/0000-0001-7225-5449	en_US
dc.date.issued	2016-01-01	en_US
dc.identifier.citation	30th AAAI Conference on Artificial Intelligence, AAAI 2016, 2016, pp. 1380 - 1386	en_US
dc.identifier.isbn	9781577357605	en_US
dc.identifier.uri	http://hdl.handle.net/10453/106117
dc.description.abstract	© 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Linear submodular bandits has been proven to be effective in solving the diversification and feature-based exploration problems in retrieval systems. Concurrently, many web-based applications, such as news article recommendation and online ad placement, can be modeled as budget-limited problems. However, the diversification problem under a budget constraint has not been considered. In this paper, we first introduce the budget constraint to linear submodular bandits as a new problem called the linear submodular bandits with a knapsack constraint. We then define an α-approximation unit-cost regret considering that submodular function maximization is NP-hard. To solve this problem, we propose two greedy algorithms based on a modified UCB rule.We then prove these two algorithms with different regret bounds and computational costs. We also conduct a number of experiments and the experimental results confirm our theoretical analyses.	en_US
dc.relation.ispartof	30th AAAI Conference on Artificial Intelligence, AAAI 2016	en_US
dc.title	Linear submodular bandits with a knapsack constraint	en_US
dc.type	Conference Proceeding
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Students
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

© 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Linear submodular bandits has been proven to be effective in solving the diversification and feature-based exploration problems in retrieval systems. Concurrently, many web-based applications, such as news article recommendation and online ad placement, can be modeled as budget-limited problems. However, the diversification problem under a budget constraint has not been considered. In this paper, we first introduce the budget constraint to linear submodular bandits as a new problem called the linear submodular bandits with a knapsack constraint. We then define an α-approximation unit-cost regret considering that submodular function maximization is NP-hard. To solve this problem, we propose two greedy algorithms based on a modified UCB rule.We then prove these two algorithms with different regret bounds and computational costs. We also conduct a number of experiments and the experimental results confirm our theoretical analyses.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/106117