Reading policies for joins: an asymptotic analysis

DOI10.1214/105051606000000646MaRDI QIDQ2467117zbMATH OpenOpenAlexFDO

Authors Ralph P. Russo, Nariankadu D. Shyamalkumar

Publication date 18 January 2008

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703019

zbMATH Keywords

bandit problemgreedy policiestax problem

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Strong limit theorems (60F15) Stopping times; optimal stopping problems; gambling theory (60G40) Markov and semi-Markov decision processes (90C40)

Abstract: Suppose that $m_n$ observations are made from the distribution $mathbfR$ and $n-m_n$ from the distribution $mathbfS$. Associate with each pair, $x$ from $mathbfR$ and $y$ from $mathbfS$, a nonnegative score $phi(x,y)$. An optimal reading policy is one that yields a sequence $m_n$ that maximizes $mathbbE(M(n))$, the expected sum of the $(n-m_n)m_n$ observed scores, uniformly in $n$. The alternating policy, which switches between the two sources, is the optimal nonadaptive policy. In contrast, the greedy policy, which chooses its source to maximize the expected gain on the next step, is shown to be the optimal policy. Asymptotics are provided for the case where the $mathbfR$ and $mathbfS$ distributions are discrete and $phi(x,y)=1or0$ according as $x=y$ or not (i.e., the observations match). Specifically, an invariance result is proved which guarantees that for a wide class of policies, including the alternating and the greedy, the variable M(n) obeys the same CLT and LIL. A more delicate analysis of the sequence $mathbbE(M(n))$ and the sample paths of M(n), for both alternating and greedy, reveals the slender sense in which the latter policy is asymptotically superior to the former, as well as a sense of equivalence of the two and robustness of the former.

Recommendations

• Optimal policies to obtain the most join results
• Optimal adaptive policies for sequential allocation problems
• scientific article; zbMATH DE number 934841
• Asymptotically efficient adaptive allocation rules
• Optimal online selection of an alternating subsequence: a central limit theorem

Cites work

• scientific article; zbMATH DE number 3885030 (Why is no real title available?)
• scientific article; zbMATH DE number 3906232 (Why is no real title available?)
• scientific article; zbMATH DE number 3720710 (Why is no real title available?)
• scientific article; zbMATH DE number 3723610 (Why is no real title available?)
• scientific article; zbMATH DE number 3502497 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 194374 (Why is no real title available?)
• Approximation Theorems of Mathematical Statistics
• Complete convergence of triangular arrays and the law of the iterated logarithm for U-statistics
• Dynamic productivity improvement in a model with multiple processes
• Extensions of the multiarmed bandit problem: The discounted case
• On the Gittins index for multiarmed bandits
• On the convergence of the empirical mass function
• Optimal policies to obtain the most join results
• Probability. Theory and examples.
• Sample path optimality for a Markov optimization problem
• Some results on increments of the Wiener process with applications to lag sums of i.i.d. random variables
• Tauberian Theory
• Upper and lower functions for martingales and mixing processes

Cited in

(1)

• Optimal policies to obtain the most join results

This page was built for publication: Reading policies for joins: an asymptotic analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467117)