From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses.
Tiapkin, D.; Belomestny, D.; Moulines, E.; Naumov, A.; Samsonov, S.; Tang, Y.; Valko, M.; and Menard, P.
In Chaudhuri, K.; Jegelka, S.; Song, L.; Szepesvari, C.; Niu, G.; and Sabato, S., editor(s),
Proceedings of the 39th International Conference on Machine Learning, volume 162, of
Proceedings of Machine Learning Research, pages 21380–21431, 17–23 Jul 2022. PMLR
![From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses [link]](//bibbase.org/img/filetypes/link.svg "Paper")
Paper
link
bibtex
abstract
@InProceedings{pmlr-v162-tiapkin22a,
title = {From {D}irichlet to Rubin: Optimistic Exploration in {RL} without Bonuses},
author = {Tiapkin, Daniil and Belomestny, Denis and Moulines, Eric and Naumov, Alexey and Samsonov, Sergey and Tang, Yunhao and Valko, Michal and Menard, Pierre},
booktitle = {Proceedings of the 39th International Conference on Machine Learning},
pages = {21380--21431},
year = {2022},
editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
volume = {162},
series = {Proceedings of Machine Learning Research},
month = {17--23 Jul},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v162/tiapkin22a/tiapkin22a.pdf},
url = {https://proceedings.mlr.press/v162/tiapkin22a.html},
abstract = {We propose the Bayes-UCBVI algorithm for reinforcement learning in tabular, stage-dependent, episodic Markov decision process: a natural extension of the Bayes-UCB algorithm by Kaufmann et al. 2012 for multi-armed bandits. Our method uses the quantile of a Q-value function posterior as upper confidence bound on the optimal Q-value function. For Bayes-UCBVI, we prove a regret bound of order $\widetilde{\mathcal{O}}(\sqrt{H^3SAT})$ where $H$ is the length of one episode, $S$ is the number of states, $A$ the number of actions, $T$ the number of episodes, that matches the lower-bound of $\Omega(\sqrt{H^3SAT})$ up to poly-$\log$ terms in $H,S,A,T$ for a large enough $T$. To the best of our knowledge, this is the first algorithm that obtains an optimal dependence on the horizon $H$ (and $S$) <em>without the need of an involved Bernstein-like bonus or noise.</em> Crucial to our analysis is a new fine-grained anti-concentration bound for a weighted Dirichlet sum that can be of independent interest. We then explain how Bayes-UCBVI can be easily extended beyond the tabular setting, exhibiting a strong link between our algorithm and Bayesian bootstrap (Rubin,1981).}
}
We propose the Bayes-UCBVI algorithm for reinforcement learning in tabular, stage-dependent, episodic Markov decision process: a natural extension of the Bayes-UCB algorithm by Kaufmann et al. 2012 for multi-armed bandits. Our method uses the quantile of a Q-value function posterior as upper confidence bound on the optimal Q-value function. For Bayes-UCBVI, we prove a regret bound of order $\widetilde{\mathcal{O}}(\sqrt{H^3SAT})$ where $H$ is the length of one episode, $S$ is the number of states, $A$ the number of actions, $T$ the number of episodes, that matches the lower-bound of $Ω(\sqrt{H^3SAT})$ up to poly-$łog$ terms in $H,S,A,T$ for a large enough $T$. To the best of our knowledge, this is the first algorithm that obtains an optimal dependence on the horizon $H$ (and $S$) without the need of an involved Bernstein-like bonus or noise. Crucial to our analysis is a new fine-grained anti-concentration bound for a weighted Dirichlet sum that can be of independent interest. We then explain how Bayes-UCBVI can be easily extended beyond the tabular setting, exhibiting a strong link between our algorithm and Bayesian bootstrap (Rubin,1981).
Solving optimal stopping problems under model uncertainty via empirical dual optimisation.
Belomestny, D.; Hübner, T.; and Krätschmer, V.
Finance Stoch., 26(3): 461–503. 2022.
Paper
doi
link
bibtex
@article {MR4447251,
AUTHOR = {Belomestny, Denis and H\"{u}bner, Tobias and Kr\"{a}tschmer, Volker},
TITLE = {Solving optimal stopping problems under model uncertainty via
empirical dual optimisation},
JOURNAL = {Finance Stoch.},
FJOURNAL = {Finance and Stochastics},
VOLUME = {26},
YEAR = {2022},
NUMBER = {3},
PAGES = {461--503},
ISSN = {0949-2984},
MRCLASS = {60G40 (60G17 90C47 91G20)},
MRNUMBER = {4447251},
DOI = {10.1007/s00780-022-00480-z},
URL = {https://doi.org/10.1007/s00780-022-00480-z},
}
A versatile deep-neural-network-based music preprocessing and remixing scheme for cochlear implant listeners.
Gauer, J.; Nagathil, A.; Eckel, K.; Belomestny, D.; and Martin, R.
Journal of the Acoustical Society of America, 151(5): 2975 – 2986. 2022.
Q1 quartile
Paper
doi
link
bibtex
@ARTICLE{Gauer20222975,
author = {Gauer, Johannes and Nagathil, Anil and Eckel, Kai and Belomestny, Denis and Martin, Rainer},
title = {A versatile deep-neural-network-based music preprocessing and remixing scheme for cochlear implant listeners},
year = {2022},
journal = {Journal of the Acoustical Society of America},
volume = {151},
number = {5},
pages = {2975 – 2986},
doi = {10.1121/10.0010371},
url = {https://www.scopus.com/inward/record.uri?eid=2-s2.0-85130096784&doi=10.1121%2f10.0010371&partnerID=40&md5=216e0907dbaad8513f25b1c64d1f1c31},
publication_stage = {Final},
note={ Q1 quartile}
}
Empirical variance minimization with applications in variance reduction and optimal control.
Belomestny, D.; Iosipoi, L.; Paris, Q.; and Zhivotovskiy, N.
Bernoulli, 28(2): 1382–1407. 2022.
Q1 quartile
Paper
doi
link
bibtex
3 downloads
@article {MR4388942,
AUTHOR = {Belomestny, Denis and Iosipoi, Leonid and Paris, Quentin and
Zhivotovskiy, Nikita},
TITLE = {Empirical variance minimization with applications in variance
reduction and optimal control},
JOURNAL = {Bernoulli},
FJOURNAL = {Bernoulli. Official Journal of the Bernoulli Society for
Mathematical Statistics and Probability},
VOLUME = {28},
YEAR = {2022},
NUMBER = {2},
PAGES = {1382--1407},
ISSN = {1350-7265},
MRCLASS = {65C20 (65K10 90C25 90C48)},
MRNUMBER = {4388942},
DOI = {10.3150/21-bej1392},
URL = {https://doi.org/10.3150/21-bej1392},
note={ Q1 quartile}
}
![From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses [link]](http://bibbase.org/img/filetypes/link.svg "Paper")
Paper
link
bibtex
abstract