## 3 A Contextual Bandit-Based Reinforcement Learning Approach
### Multi-Armed Bandits: Balancing Exploration and Exploitation  
Multi-armed bandits (MABs) represent a foundational paradigm in reinforcement learning that equips decision-making algorithms to handle uncertainty [53; 54]. The overarching challenge within MAB scenarios is to negotiate the trade-off between choosing known options that yield consistently good results (\"exploitation\") and experimenting with less familiar alternatives in pursuit of even better outcomes (\"exploration\"). MAB problems typically involve three main elements: (1) a selection mechanism that identifies which action to take next, (2) a reward function that quantifies the outcome, and (3) a set of available options (the \"arms\" of the bandit). To illustrate how MABs can be applied, imagine a router tasked with directing network traffic along multiple possible paths. Because Internet latency can vary over time, sometimes periodically or unpredictably, selecting a route that provides the best performance at a given moment becomes non-trivial. With an MAB, the router repeatedly picks one route (an action) from its collection of options. In return, it observes a reward reflecting the overall latency. The algorithm must intelligently alternate between relying on routes known to be fast and attempting less frequently used routes in case they have recently become better. By doing so, it strives to find the top-performing route under the current conditions, even if that condition is characterized by generally high latency. This work explores three selection strategies commonly employed in MAB contexts, as outlined below:  
* Boltzmann Exploration (Softmax): Boltzmann exploration, or Softmax action [55], relies on probabilistic decision-making. Each available action is associated with an expected return, and these values are transformed into a probability distribution: \[P(a_{i})=\frac{e^{V(a_{i})/\tau}}{\sum_{j=1}^{n}1e^{v(a_{j})/\tau}}\] where \(P(a_{i})\) is the likelihood of choosing action \(a_{i}\), and \(\tau\) (the temperature parameter) determines how evenly spread these probabilities are. A lower \(\tau\) makes the algorithm more strongly favor the highest-valued actions, while a higher \(\tau\) encourages the algorithm to sample more evenly, effectively promoting exploration. An action is then selected by sampling according to these probabilities, ensuring that even actions with lower values can still occasionally be tested. To mitigate overfitting during this process, the Softmax strategy is executed over multiple randomized iterations and leverages exploration dynamics to avoid convergence on a narrow subset of boundaries too early in the learning cycle. * Upper Confidence Bound (UCB): UCB is a deterministic selection approach that balances the known performance of actions with the uncertainty associated with them. At each decision point, the algorithm calculates an uncertainty factor for each action based on how frequently it has been chosen relative to the total number of trials. Specifically, if \(t\) is the current trial count and \(nt(a)\) is how many times an action \(a\) has been chosen, the uncertainty term is given by \[r_{t}(a)=\sqrt{\frac{2\log t}{n_{t}(a)}}\]
* Combining the action's average reward with this uncertainty measure yields a final score. Actions that have been selected less often carry higher uncertainty values, making them more appealing to try. Over time, all actions are tested, and the strategy hones in on the subset of actions that yield the best results. Importantly, UCB's built-in confidence bounds function as a natural regularizer, helping to prevent overfitting by encouraging the exploration of less frequently selected boundaries
* Thompson Sampling: Thompson sampling leverages Bayesian updating to determine which action to select. The algorithm models the reward distribution of each action (often using a beta distribution in the case of binary rewards) and, at each decision step, samples from these distributions to choose the action that seems most promising.