Answers.Body: <blockquote>
  <p>Isn't the distribution independent of the time the arm <span class="math-container">$i$</span> was chosen?</p>
  </blockquote>
  <p>Each one of the two references you describe assumes the context of the random bandit problem proposed by <a href="https://projecteuclid.org/euclid.bams/1183517370" rel="nofollow noreferrer">Robbins (1952)</a> where the underlying reward distributions of each bandit are fixed. Therefore, <strong>yes</strong>, the underlying distributions are independent of the current time.</p>
  <blockquote>
  <p>Is it because the chosen arm at step <span class="math-container">$t$</span> (namely <span class="math-container">$I_t$</span>) is a random variable and <span class="math-container">$X$</span> depends on it?</p>
  </blockquote>
  <p>The reward is a random variable which is dependent on the chosen arm at time <span class="math-container">$t$</span>. Since each arm has an underlying reward distribution, the index <span class="math-container">$I_t$</span> is a random variable that designates the specific arm we are pulling, and the index <span class="math-container">$t$</span> denotes the time step when we pull the arm.</p>
  <blockquote>
  <p>Why is <span class="math-container">$t$</span> used twice in the index (namely <span class="math-container">$I_t,t$</span>)?</p>
  </blockquote>
  <p>Note that <span class="math-container">$t$</span> is used twice, but the observed value of <span class="math-container">$I_t$</span> <strong>does not encode any information about the time it was chosen</strong>. For example, if <span class="math-container">$I_m = 5$</span>, then <span class="math-container">$X_{I_m,\ m} = X_{5,\ m}$</span>. If we drop the second subscript, then we have no way to distinguish <span class="math-container">$X_{5,\ m}$</span> notationally from <span class="math-container">$X_{5,\ n}$</span> (where <span class="math-container">$I_{n\ \neq\ m} = 5$</span>). Two distinct rewards <span class="math-container">$X_{5,\ m}$</span> and <span class="math-container">$X_{5,\ n}$</span> would map to the same reward <span class="math-container">$X_5$</span> notationally. At first glance, this introduces numerous potential notational problems, such as losing the count of the number of times each arm was pulled.</p>
  <blockquote>
  <p>Why not simply use <span class="math-container">$X_i$</span> instead of <span class="math-container">$X_{I_t,\ t}$</span> (in terms of rewards)? Shouldn't <span class="math-container">$X_{I_t}$</span> be sufficient, since <span class="math-container">$X_{I_t,\ m}$</span> and <span class="math-container">$X_{I_t,\ n}$</span> are drawn from the same distribution?</p>
  </blockquote>
  <p>Admittedly, there are probably ways to get around the extra subscript for certain algorithms. For example, maybe you are using an algorithm where past rewards from each arm are averaged to yield an estimate of each arm's expected reward (see Section 2.2 of <a href="http://www.incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton and Barto</a>). This may require a collection of lists that store the past rewards for each arm, or it may require the count of each arm being pulled and an associated current estimate of the expected reward (see Section 2.4 of Sutton and Barto). However, <strong>these methods introduce more parameters that would be unnecessary had we initially included a second subscript for time in our notation</strong> (e.g. the counts of each arm pulled, the current estimate of expected reward for each arm, the labels of each reward list corresponding to an arm, etc.). Most of the fundamental equations regarding multi-armed bandits that I have seen are either <strong>heavily or solely dependent on the reward random variable</strong> (e.g. the definition of regret). Keeping the time index in a single random variable <strong>promotes concision and consistency</strong> among various sources by <strong>preventing the need for delegating the time index to another random variable, data structure, etc.</strong>, even though specific implementations or contexts may profit from other notations.</p>
  <p>The dual-subscript notation also has the benefit of generalizing to other contexts aside from the one posed by Robbins (1952). These include nonstationary reward distributions (see Section 2.5 of Sutton and Barto), time discounting, and families of alternative bandit processes, among others (see Sections 2.2-2.4 of <a href="https://onlinelibrary.wiley.com/doi/book/10.1002/9780470980033" rel="nofollow noreferrer">this book</a> for info on the last two extensions).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-16T21:08:48.407Z
Answers.LastActivityDate: 2020-07-16T21:08:48.407Z
Answers.UserDisplayName: DeepQZero
Answers.Body: <blockquote>
  <p>Isn't the distribution independent of the time the arm <span class="math-container">$i$</span> was chosen?</p>
  </blockquote>
  <p>Yes, but you don't know which arm was chosen at time <span class="math-container">$t$</span>, that is what <span class="math-container">$I_t$</span> represents. <span class="math-container">$v_i$</span> would represent the <span class="math-container">$i$</span>th arms distribution, whereas you want the distribution of the arm that was chosen at time <span class="math-container">$t$</span>, which is <span class="math-container">$v_{I_t}$</span>.</p>
  <p><span class="math-container">$X_{I_t,t}$</span> is used to represent the arm you chose at time <span class="math-container">$t$</span> and the time you chose it. Imagine if we chose the following arms at respective time steps {1,2,5,2,4}, then the reward you get at time 3 (assuming in my example time started at 1) would be <span class="math-container">$X_{5,3}$</span>. You need this notation because every time you pull arm <span class="math-container">$i$</span> you get a different reward, because the reward is a random variable (unless the assumption was a deterministic reward but that would not be interesting).</p>
  <p>It has been a while since I read the papers but I assume that the distributions of the arms are stationary, however this notation is more general and would allow for non-stationary distributions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-16T17:03:25.090Z
Answers.LastActivityDate: 2020-07-16T21:14:58.073Z
Answers.LastEditDate: 2020-07-16T21:14:58.073Z
Answers.UserDisplayName: David
Body: <p>I'm doing some introductory research on classical (stochastic) MABs. However, I'm a little confused about the common notation (e.g. in the popular paper of <a href="https://homes.di.unimi.it/cesa-bianchi/Pubblicazioni/ml-02.pdf" rel="nofollow noreferrer">Auer (2002)</a> or <a href="https://arxiv.org/pdf/1204.5721.pdf" rel="nofollow noreferrer">Bubeck and Cesa-Bianchi (2012)</a>).</p>
  <p>As in the latter study, let us consider an MAB with a finite number of arms <span class="math-container">$i\in\{1,...,K\}$</span>, where an agent choses at every timestep <span class="math-container">$t=1,...,n$</span> an arm <span class="math-container">$I_t$</span> which generates a reward <span class="math-container">$X_{I_t,t}$</span> according to a distribition <span class="math-container">$v_{I_t}$</span>.</p>
  <p>In my understanding, each arm has an inherent distribution, which is unknown to the agent. Therefore, I'm wondering why the notation <span class="math-container">$v_{I_t}$</span> is used instead of simply using <span class="math-container">$v_{i}$</span>? Isn't the distribution independent of the <strong>time</strong> the arm <span class="math-container">$i$</span> was chosen?</p>
  <p>Furthermore, I ask myself: Why not simply use <span class="math-container">$X_i$</span> instead of <span class="math-container">$X_{I_t,t}$</span> (in terms of rewards). Is it because the chosen arm at step <span class="math-container">$t$</span> (namely <span class="math-container">$I_t$</span>) is a random variable and <span class="math-container">$X$</span> depends on it? If I am right, why is <span class="math-container">$t$</span> used twice in the index (namely <span class="math-container">$I_t,t$</span>)?
  Shouldn't <span class="math-container">$X_{I_t}$</span> be sufficient, since <span class="math-container">$X_{I_t,m}$</span> and <span class="math-container">$X_{I_t,n}$</span> are drawn from the same distribution?</p>
  
Tags: <papers><notation><multi-armed-bandits><upper-confidence-bound>
Title: Why do we use $X_{I_t,t}$ and $v_{I_t}$ to denote the reward received and the at time step $t$ and the distribution of the chosen arm $I_t$?
UserDisplayName: MAB_N00B
ThreadText: # Why do we use $X_{I_t,t}$ and $v_{I_t}$ to denote the reward received and the at time step $t$ and the distribution of the chosen arm $I_t$?
  
  (Asked by: username_0 on 2020-07-16)
  
  I'm doing some introductory research on classical (stochastic) MABs. However, I'm a little confused about the common notation (e.g. in the popular paper of [Auer (2002)](https://homes.di.unimi.it/cesa-bianchi/Pubblicazioni/ml-02.pdf) or [Bubeck and Cesa-Bianchi (2012)](https://arxiv.org/pdf/1204.5721.pdf)).
  
  As in the latter study, let us consider an MAB with a finite number of arms $i\in\{1,...,K\}$, where an agent choses at every timestep $t=1,...,n$ an arm $I\_t$ which generates a reward $X\_{I\_t,t}$ according to a distribition $v\_{I\_t}$.
  
  In my understanding, each arm has an inherent distribution, which is unknown to the agent. Therefore, I'm wondering why the notation $v\_{I\_t}$ is used instead of simply using $v\_{i}$? Isn't the distribution independent of the **time** the arm $i$ was chosen?
  
  Furthermore, I ask myself: Why not simply use $X\_i$ instead of $X\_{I\_t,t}$ (in terms of rewards). Is it because the chosen arm at step $t$ (namely $I\_t$) is a random variable and $X$ depends on it? If I am right, why is $t$ used twice in the index (namely $I\_t,t$)?
  Shouldn't $X\_{I\_t}$ be sufficient, since $X\_{I\_t,m}$ and $X\_{I\_t,n}$ are drawn from the same distribution?
  
  **Tags:** papers, notation, multi-armed-bandits, upper-confidence-bound
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-07-16. Score: 2
  
  > Isn't the distribution independent of the time the arm $i$ was chosen?
  
  Each one of the two references you describe assumes the context of the random bandit problem proposed by [Robbins (1952)](https://projecteuclid.org/euclid.bams/1183517370) where the underlying reward distributions of each bandit are fixed. Therefore, **yes**, the underlying distributions are independent of the current time.
  
  > Is it because the chosen arm at step $t$ (namely $I\_t$) is a random variable and $X$ depends on it?
  
  The reward is a random variable which is dependent on the chosen arm at time $t$. Since each arm has an underlying reward distribution, the index $I\_t$ is a random variable that designates the specific arm we are pulling, and the index $t$ denotes the time step when we pull the arm.
  
  > Why is $t$ used twice in the index (namely $I\_t,t$)?
  
  Note that $t$ is used twice, but the observed value of $I\_t$ **does not encode any information about the time it was chosen**. For example, if $I\_m = 5$, then $X\_{I\_m,\ m} = X\_{5,\ m}$. If we drop the second subscript, then we have no way to distinguish $X\_{5,\ m}$ notationally from $X\_{5,\ n}$ (where $I\_{n\ \neq\ m} = 5$). Two distinct rewards $X\_{5,\ m}$ and $X\_{5,\ n}$ would map to the same reward $X\_5$ notationally. At first glance, this introduces numerous potential notational problems, such as losing the count of the number of times each arm was pulled.
  
  > Why not simply use $X\_i$ instead of $X\_{I\_t,\ t}$ (in terms of rewards)? Shouldn't $X\_{I\_t}$ be sufficient, since $X\_{I\_t,\ m}$ and $X\_{I\_t,\ n}$ are drawn from the same distribution?
  
  Admittedly, there are probably ways to get around the extra subscript for certain algorithms. For example, maybe you are using an algorithm where past rewards from each arm are averaged to yield an estimate of each arm's expected reward (see Section 2.2 of [Sutton and Barto](http://www.incompleteideas.net/book/the-book-2nd.html)). This may require a collection of lists that store the past rewards for each arm, or it may require the count of each arm being pulled and an associated current estimate of the expected reward (see Section 2.4 of Sutton and Barto). However, **these methods introduce more parameters that would be unnecessary had we initially included a second subscript for time in our notation** (e.g. the counts of each arm pulled, the current estimate of expected reward for each arm, the labels of each reward list corresponding to an arm, etc.). Most of the fundamental equations regarding multi-armed bandits that I have seen are either **heavily or solely dependent on the reward random variable** (e.g. the definition of regret). Keeping the time index in a single random variable **promotes concision and consistency** among various sources by **preventing the need for delegating the time index to another random variable, data structure, etc.**, even though specific implementations or contexts may profit from other notations.
  
  The dual-subscript notation also has the benefit of generalizing to other contexts aside from the one posed by Robbins (1952). These include nonstationary reward distributions (see Section 2.5 of Sutton and Barto), time discounting, and families of alternative bandit processes, among others (see Sections 2.2-2.4 of [this book](https://onlinelibrary.wiley.com/doi/book/10.1002/9780470980033) for info on the last two extensions).
  
  
  ---
  
  ### Answer by username_2 on 2020-07-16. Score: 2
  
  > Isn't the distribution independent of the time the arm $i$ was chosen?
  
  Yes, but you don't know which arm was chosen at time $t$, that is what $I\_t$ represents. $v\_i$ would represent the $i$th arms distribution, whereas you want the distribution of the arm that was chosen at time $t$, which is $v\_{I\_t}$.
  
  $X\_{I\_t,t}$ is used to represent the arm you chose at time $t$ and the time you chose it. Imagine if we chose the following arms at respective time steps {1,2,5,2,4}, then the reward you get at time 3 (assuming in my example time started at 1) would be $X\_{5,3}$. You need this notation because every time you pull arm $i$ you get a different reward, because the reward is a random variable (unless the assumption was a deterministic reward but that would not be interesting).
  
  It has been a while since I read the papers but I assume that the distributions of the arms are stationary, however this notation is more general and would allow for non-stationary distributions.
  
  
  ---
  
  