Learning and Optimization with Seasonal Patterns

• URL: http://arxiv.org/abs/2005.08088v4
• Date: Sun, 22 Aug 2021 14:28:47 GMT
• Title: Learning and Optimization with Seasonal Patterns
• Authors: Ningyuan Chen, Chun Wang, Longlin Wang
• Abstract summary: We consider a nonstationary MAB model with $K$ arms whose mean rewards vary over time in a periodic manner. We propose a two-stage policy that combines a confidence-bound analysis with a learning procedure to learn the unknown periods. We show that our learning policy incurs a regret upper bound $tildeO(sqrtTsum_k=1K T_k)$ where $T_k$ is the period of arm $k$.
• Score: 3.7578900993400626
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A standard assumption adopted in the multi-armed bandit (MAB) framework is that the mean rewards are constant over time. This assumption can be restrictive in the business world as decision-makers often face an evolving environment where the mean rewards are time-varying. In this paper, we consider a non-stationary MAB model with $K$ arms whose mean rewards vary over time in a periodic manner. The unknown periods can be different across arms and scale with the length of the horizon $T$ polynomially. We propose a two-stage policy that combines the Fourier analysis with a confidence-bound-based learning procedure to learn the periods and minimize the regret. In stage one, the policy correctly estimates the periods of all arms with high probability. In stage two, the policy explores the periodic mean rewards of arms using the periods estimated in stage one and exploits the optimal arm in the long run. We show that our learning policy incurs a regret upper bound $\tilde{O}(\sqrt{T\sum_{k=1}^K T_k})$ where $T_k$ is the period of arm $k$. Moreover, we establish a general lower bound $\Omega(\sqrt{T\max_{k}\{ T_k\}})$ for any policy. Therefore, our policy is near-optimal up to a factor of $\sqrt{K}$.

Related papers

• Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
  Graph-Triggered Bandits is a framework to generalize rested and restless bandits. In this work, we focus on two specific types of monotonic bandits: rising, where the expected reward of an arm grows as the number of triggers increases, and rotting, where the opposite behavior occurs.
  arXiv  Detail & Related papers  (2024-09-09T18:23:07Z)
• Multi-Armed Bandits with Interference [39.578572123342944]
  We show that switchback policies achieve an optimal em expected regret $tilde O(sqrt T)$ against the best fixed-arm policy. We propose a cluster randomization policy whose regret is optimal in em expectation.
  arXiv  Detail & Related papers  (2024-02-02T19:02:47Z)
• Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
  We consider a decision maker allocating one unit of renewable and divisible resource in each period on a number of arms. The arms have unknown and random rewards whose means are proportional to the allocated resource and whose variances are proportional to an order $b$ of the allocated resource.
  arXiv  Detail & Related papers  (2023-06-28T21:59:11Z)
• Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption [12.471848976031904]
  A fundamental goal is to efficiently compute policies that achieve a diminishing optimality gap as the number of arms, $N$, grows large. Existing results on optimality all rely on the uniform global attractor property (UGAP), a complex and challenging-to-verify assumption. We propose a general, simulation-based framework, that converts any single-armed policy into a policy for the original $N$-armed problem.
  arXiv  Detail & Related papers  (2023-05-31T21:26:43Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  We study a distributed multi-armed bandit where a client supplies the learner with communication-constrained feedback. We propose a multi-phase bandit algorithm, $mathttUEtext-UCB++$, which matches this lower bound to a minor additive factor.
  arXiv  Detail & Related papers  (2023-04-25T09:31:20Z)
• Tractable Optimality in Episodic Latent MABs [75.17357040707347]
  We consider a multi-armed bandit problem with $M$ latent contexts, where an agent interacts with the environment for an episode of $H$ time steps. Depending on the length of the episode, the learner may not be able to estimate accurately the latent context. We design a procedure that provably learns a near-optimal policy with $O(textttpoly(A) + texttttpoly(M,H)min(M,H))$ interactions.
  arXiv  Detail & Related papers  (2022-10-05T22:53:46Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  We consider a multi-armed bandit setting where, at the beginning of each round, the learner receives noisy independent evaluations of the true reward of each arm. We derive different algorithmic approaches and theoretical guarantees depending on how the evaluations are generated.
  arXiv  Detail & Related papers  (2021-12-13T09:48:54Z)
• Continuous Time Bandits With Sampling Costs [17.412117389855222]
  We consider a continuous-time multi-arm bandit problem (CTMAB), where the learner can sample arms any number of times in a given interval and obtain a random reward from each sample. There is a tradeoff between obtaining large reward and incurring sampling cost as a function of the sampling frequency. The goal is to design a learning algorithm that minimizes regret, that is defined as the difference of the payoff of the oracle policy and that of the learning algorithm.
  arXiv  Detail & Related papers  (2021-07-12T10:00:35Z)
• Dynamic Planning and Learning under Recovering Rewards [18.829837839926956]
  We propose, construct and prove performance guarantees for a class of "Purely Periodic Policies" Our framework and policy design may have the potential to be adapted into other offline planning and online learning applications.
  arXiv  Detail & Related papers  (2021-06-28T15:40:07Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  We present a reward model that captures set-dependent reward distribution and assumes no total order for arms. We develop a novel regret analysis and show an $Oleft(frack2 n log Tepsilonright)$ gap-dependent regret bound as well as an $Oleft(k2sqrtn T log Tright)$ gap-independent regret bound.
  arXiv  Detail & Related papers  (2021-03-03T23:08:59Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  We study the top-$k$ extreme contextual bandits problem, where the total number of arms can be enormous. We first propose an algorithm for the non-extreme realizable setting, utilizing the Inverse Gap Weighting strategy. We show that our algorithm has a regret guarantee of $O(ksqrt(A-k+1)T log (|mathcalF|T))$.
  arXiv  Detail & Related papers  (2021-02-15T19:10:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.