Random Walk Approach to Regret Minimization
We propose a computationally efficient random walk on a convex body which rapidly mixes to a time-varying Gibbs distribution. In the setting of online convex optimization and repeated games, the algorithm yields low regret and presents a novel efficient method for implementing mixture forecasting strategies.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Stochastic Gradient Descent on a Tree: an Adaptive and Robust Approach to Stochastic Convex Optimization
Online minimization of an unknown convex function over the interval $[0,1]$ is considered under first-order stochastic bandit feedback, which returns a random realization of the gradient of the function at each query poi…
Fitting mixed logit random regret minimization models using maximum simulated likelihood
This article describes the mixrandregret command, which extends the randregret command introduced in Guti\'errez-Vargas et al. (2021, The Stata Journal 21: 626-658) incorporating random coefficients for Random Regret Min…
Numerical IntegrationOptimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice
We prove non-asymptotic lower bounds on the expectation of the maximum of $d$ independent Gaussian variables and the expectation of the maximum of $d$ independent symmetric random walks. Both lower bounds recover the opt…
Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration
This paper studies regret minimization with randomized value functions in reinforcement learning. In tabular finite-horizon Markov Decision Processes, we introduce a clipping variant of one classical Thompson Sampling (T…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Thompson SamplingTowards Optimal Algorithms for Prediction with Expert Advice
We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. In 1965, Cover gave the optimal algorithm for the case of 2 experts. In this paper, we design the…
PredictionThompson Sampling