We borrow standard notations from [1]}, that we will include in this section for quick reference.
To provide a fair comparison between our algorithm and the \(Q\) -learning with UCB-Hoeffding algorithm, proposed by [1]}, we maintain a similar problem setting.
Extending this work to other settings (e.g., stochastic reward, terminating states, discounting, etc.) is left for future work.
We begin by describing the Markov decision process, MDP\((\mathcal {S}, \mathcal {A}, H, \mathbb {P}, r)\) .
The set of states is \(\mathcal {S}\) , with \(|\mathcal {S}| = S\) .
The set of actions is \(\mathcal {A}\) , with \(|\mathcal {A}| = A\) . The number of steps per episode (horizon) is \(H\) .
The transition dynamics are given by \(\mathbb {P}\) , where \(\mathbb {P}_h(\cdot |x, a)\)  gives the next state distribution if action \(a\)  was taken in state \(x\)  at step \(h \in [H]\) .
The deterministic reward function is \(r_h(x, a)\) , which provides a reward in the range \([0, 1]\)  for taking action \(a\)  in state \(x\)  at step \(h\) .
The agent acts in this MDP for \(K\)  episodes. We let \(T = K H\)  denote the total number of steps the agent takes in the MDP.
