Online learning over a finite action set with limited switching
This paper studies the value of switching actions in the Prediction From Experts (PFE) problem and Adversarial Multi-Armed Bandits (MAB) problem. First, we revisit the well-studied and practically motivated setting of PFE with switching costs. Many algorithms are known to achieve the minimax optimal...
Uloženo v:
| Hlavní autoři: | , |
|---|---|
| Médium: | Článek |
| Vydáno: |
2018
|
| Témata: | |
| On-line přístup: | https://arxiv.org/abs/1803.01548 http://arxiv.org/abs/1803.01548 |
| Tagy: |
Žádné tagy, Buďte první, kdo vytvoří štítek k tomuto záznamu!
|
| _version_ | 1879173373641097216 |
|---|---|
| author | Altschuler, Jason Talwar, Kunal |
| author_browse | Altschuler, Jason Talwar, Kunal |
| author_facet | Altschuler, Jason Talwar, Kunal |
| author_sort | Altschuler, Jason |
| building | arXiv |
| collection | Acceso abierto |
| description | This paper studies the value of switching actions in the Prediction From Experts (PFE) problem and Adversarial Multi-Armed Bandits (MAB) problem. First, we revisit the well-studied and practically motivated setting of PFE with switching costs. Many algorithms are known to achieve the minimax optimal order of $O(\sqrt{T \log n})$ in expectation for both regret and number of switches, where $T$ is the number of iterations and $n$ the number of actions. However, no high probability (h.p.) guarantees are known. Our main technical contribution is the first algorithms which with h.p. achieve this optimal order for both regret and switches. This settles an open problem of [Devroye et al., 2015], and directly implies the first h.p. guarantees for several problems of interest.
Next, to investigate the value of switching actions at a more granular level, we introduce the setting of switching budgets, in which algorithms are limited to $S \leq T$ switches between actions. This entails a limited number of free switches, in contrast to the unlimited number of expensive switches in the switching cost setting. Using the above result and several reductions, we unify previous work and completely characterize the complexity of this switching budget setting up to small polylogarithmic factors: for both PFE and MAB, for all switching budgets $S \leq T$, and for both expectation and h.p. guarantees. For PFE, we show the optimal rate is $\tildeΘ(\sqrt{T\log n})$ for $S = Ω(\sqrt{T\log n})$, and $\min(\tildeΘ(\tfrac{T\log n}{S}), T)$ for $S = O(\sqrt{T \log n})$. Interestingly, the bandit setting does not exhibit such a phase transition; instead we show the minimax rate decays steadily as $\min(\tildeΘ(\tfrac{T\sqrt{n}}{\sqrt{S}}), T)$ for all ranges of $S \leq T$. These results recover and generalize the known minimax rates for the (arbitrary) switching cost setting. |
| doi_str_mv | 10.1287/moor.2020.1052 |
| first_indexed | 2026-10-15T23:56:12Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-1803.01548</identifier><datestamp>2021-11-16</datestamp>
<dc:title>Online learning over a finite action set with limited switching</dc:title>
<dc:creator>Altschuler, Jason</dc:creator>
<dc:creator>Talwar, Kunal</dc:creator>
<dc:subject>Machine Learning</dc:subject>
<dc:subject>Optimization and Control</dc:subject>
<dc:description>This paper studies the value of switching actions in the Prediction From Experts (PFE) problem and Adversarial Multi-Armed Bandits (MAB) problem. First, we revisit the well-studied and practically motivated setting of PFE with switching costs. Many algorithms are known to achieve the minimax optimal order of $O(\sqrt{T \log n})$ in expectation for both regret and number of switches, where $T$ is the number of iterations and $n$ the number of actions. However, no high probability (h.p.) guarantees are known. Our main technical contribution is the first algorithms which with h.p. achieve this optimal order for both regret and switches. This settles an open problem of [Devroye et al., 2015], and directly implies the first h.p. guarantees for several problems of interest.
Next, to investigate the value of switching actions at a more granular level, we introduce the setting of switching budgets, in which algorithms are limited to $S \leq T$ switches between actions. This entails a limited number of free switches, in contrast to the unlimited number of expensive switches in the switching cost setting. Using the above result and several reductions, we unify previous work and completely characterize the complexity of this switching budget setting up to small polylogarithmic factors: for both PFE and MAB, for all switching budgets $S \leq T$, and for both expectation and h.p. guarantees. For PFE, we show the optimal rate is $\tildeΘ(\sqrt{T\log n})$ for $S = Ω(\sqrt{T\log n})$, and $\min(\tildeΘ(\tfrac{T\log n}{S}), T)$ for $S = O(\sqrt{T \log n})$. Interestingly, the bandit setting does not exhibit such a phase transition; instead we show the minimax rate decays steadily as $\min(\tildeΘ(\tfrac{T\sqrt{n}}{\sqrt{S}}), T)$ for all ranges of $S \leq T$. These results recover and generalize the known minimax rates for the (arbitrary) switching cost setting. </dc:description>
<dc:description>Extended abstract to appear in the proceedings of the 2018 Conference on Learning Theory (COLT)</dc:description>
<dc:date>2018-03-05</dc:date>
<dc:date>2018-06-13</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/1803.01548</dc:identifier>
<dc:identifier>http://arxiv.org/abs/1803.01548</dc:identifier>
<dc:identifier>Mathematics of Operations Research, 46(1), 179-203, 2021</dc:identifier>
<dc:identifier>doi:10.1287/moor.2020.1052</dc:identifier>
</oai_dc:dc> |
| id | arxiv-1803.01548 |
| institution | arXiv |
| last_indexed | 2026-10-15T23:56:12Z |
| publishDate | 2018 |
| publishDateRange | 2018 |
| publishDateSort | 2018 |
| record_format | oai_dc |
| spelling | arxiv-1803.015482021-11-16 Online learning over a finite action set with limited switching Altschuler, Jason Talwar, Kunal Machine Learning Optimization and Control This paper studies the value of switching actions in the Prediction From Experts (PFE) problem and Adversarial Multi-Armed Bandits (MAB) problem. First, we revisit the well-studied and practically motivated setting of PFE with switching costs. Many algorithms are known to achieve the minimax optimal order of $O(\sqrt{T \log n})$ in expectation for both regret and number of switches, where $T$ is the number of iterations and $n$ the number of actions. However, no high probability (h.p.) guarantees are known. Our main technical contribution is the first algorithms which with h.p. achieve this optimal order for both regret and switches. This settles an open problem of [Devroye et al., 2015], and directly implies the first h.p. guarantees for several problems of interest. Next, to investigate the value of switching actions at a more granular level, we introduce the setting of switching budgets, in which algorithms are limited to $S \leq T$ switches between actions. This entails a limited number of free switches, in contrast to the unlimited number of expensive switches in the switching cost setting. Using the above result and several reductions, we unify previous work and completely characterize the complexity of this switching budget setting up to small polylogarithmic factors: for both PFE and MAB, for all switching budgets $S \leq T$, and for both expectation and h.p. guarantees. For PFE, we show the optimal rate is $\tildeΘ(\sqrt{T\log n})$ for $S = Ω(\sqrt{T\log n})$, and $\min(\tildeΘ(\tfrac{T\log n}{S}), T)$ for $S = O(\sqrt{T \log n})$. Interestingly, the bandit setting does not exhibit such a phase transition; instead we show the minimax rate decays steadily as $\min(\tildeΘ(\tfrac{T\sqrt{n}}{\sqrt{S}}), T)$ for all ranges of $S \leq T$. These results recover and generalize the known minimax rates for the (arbitrary) switching cost setting. Extended abstract to appear in the proceedings of the 2018 Conference on Learning Theory (COLT) 2018-03-05 2018-06-13 text https://arxiv.org/abs/1803.01548 http://arxiv.org/abs/1803.01548 Mathematics of Operations Research, 46(1), 179-203, 2021 doi:10.1287/moor.2020.1052 |
| spellingShingle | Machine Learning Optimization and Control Altschuler, Jason Talwar, Kunal Online learning over a finite action set with limited switching |
| title | Online learning over a finite action set with limited switching |
| title_full | Online learning over a finite action set with limited switching |
| title_fullStr | Online learning over a finite action set with limited switching |
| title_full_unstemmed | Online learning over a finite action set with limited switching |
| title_short | Online learning over a finite action set with limited switching |
| title_sort | online learning over a finite action set with limited switching |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/1803.01548 http://arxiv.org/abs/1803.01548 |
| work_keys_str_mv | AT altschulerjason onlinelearningoverafiniteactionsetwithlimitedswitching AT talwarkunal onlinelearningoverafiniteactionsetwithlimitedswitching |