Satsangi, Yash, Whiteson, Shimon and Oliehoek, Frans A 
ORCID: 0000-0003-4372-5055
(2016)
Probably Approximately Correct Greedy Maximization.
AAMAS'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, abs/16.
pp. 1387-1388.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1602.07860v1.pdf - Unspecified Download (326kB) |
Abstract
Submodular function maximization finds application in a variety of real-world decision-making problems. However, most existing methods, based on greedy maximization, assume it is computationally feasible to evaluate F, the function being maximized. Unfortunately, in many realistic settings F is too expensive to evaluate exactly even once. We present probably approximately correct greedy maximization, which requires access only to cheap anytime confidence bounds on F and uses them to prune elements. We show that, with high probability, our method returns an approximately optimal set. We propose novel, cheap confidence bounds for conditional entropy, which appears in many common choices of F and for which it is difficult to find unbiased or bounded estimates. Finally, results on a real-world dataset from a multi-camera tracking system in a shopping mall demonstrate that our approach performs comparably to existing methods, but at a fraction of the computational cost.
| Item Type: | Article |
|---|---|
| Additional Information: | (Extended Abstract) To appear. wwwnote: [Please also see the <a href="https://arxiv.org/abs/1602.07860">extended version on arXiv</a>, as well as the <a href="b2hd-Satsangi16IJCAI.html"> IJCAI version</a>.] |
| Uncontrolled Keywords: | Submodularity, Greedy maximization, Sensor scheduling, Planning |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 Apr 2016 11:04 |
| Last Modified: | 15 Dec 2022 22:06 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3000365 |
Share
Share
