<jupyter_start><jupyter_text>Budgeted bandits  Import libraries<jupyter_code>import numpy as np
import random
import time
from posterior.Beta import Beta as BetaPosterior<jupyter_output><empty_output><jupyter_text>Environment<jupyter_code>class Bernoulli:
    """ Bernoulli distributed arm """

    def __init__(self, expectation, cost):
        self.expectation = expectation
        self.cost = cost
        
    def draw(self):
        return float(random.random() < self.expectation), float(random.random() < self.cost)
class Beta:
    """ Beta distributed arm """

    def __init__(self, a_reward, b_reward, a_cost, b_cost):
        self.a_reward = a_reward
        self.b_reward = b_reward
        self.expectation = a_reward / (a_reward + b_reward)
        self.a_cost = a_cost
        self.b_cost = b_cost
        self.cost = a_cost / (a_cost + b_cost)
        
    def draw(self):
        return random.betavariate(self.a_reward, self.b_reward), random.betavariate(self.a_cost, self.b_cost)
class ResultBudgetedMAB:
    def __init__(self):
        self.rewards = []
        self.costs = []

    def store(self, reward, cost):
        self.rewards += [reward]
        self.costs += [cost]
    

class BudgetedMAB:
    def __init__(self, arms, budget):
        self.arms = arms
        self.nb_arms = len(arms)
        self.initial_budget = budget

    def play(self, algo):
        budget = self.initial_budget
        algo.start_game()
        result = ResultBudgetedMAB()
        
        while budget >= 0:
            choice = algo.choice()
            reward, cost = self.arms[choice].draw()
            algo.get_reward(choice, reward, cost)
            budget -= cost
            if budget >= 0:
                result.store(self.arms[choice].expectation, self.arms[choice].cost)
            
        return result
class EvaluationBudgetedMAB:
    def __init__(self, env, algo, nb_repetitions):
        self.env = env
        self.nb_repetitions = nb_repetitions
        self.cum_reward = [[] for _ in range(self.nb_repetitions)]

        for k in range(nb_repetitions):
            if nb_repetitions < 10 or k % (nb_repetitions / 10) == 0:
                print(k)
            result = env.play(algo)
            self.cum_reward[k] = np.cumsum(result.rewards)
    
    def mean_reward(self):
        return np.mean([self.cum_reward[k][-1] for k in range(self.nb_repetitions)])
    
    def mean_regret(self):
        oracle = self.env.initial_budget * np.max([arm.expectation / arm.cost for arm in self.env.arms])
        temp = np.array([self.cum_reward[k][-1] for k in range(self.nb_repetitions)])
        return oracle - np.mean(temp), np.std(oracle - temp)
class EvaluationBayesBudgetedMAB:
    def __init__(self, envs, algo):
        self.nb_repetitions = len(envs)
        self.cum_reward = np.zeros(self.nb_repetitions)
        self.oracle = np.zeros(self.nb_repetitions)

        for k in range(self.nb_repetitions):
            if self.nb_repetitions < 10 or k % (self.nb_repetitions / 10) == 0:
                print(k)
                
            result = envs[k].play(algo)
            self.cum_reward[k] = np.cumsum(result.rewards)[-1]
            self.oracle[k] = envs[k].initial_budget * np.max([arm.expectation / arm.cost for arm in envs[k].arms])
            
    def mean_final_regret(self):
        temp = self.oracle - self.cum_reward
        return np.mean(temp), np.std(temp)<jupyter_output><empty_output><jupyter_text>Algorithms<jupyter_code>class BTS:
    """
        Ref: Thompson sampling for budgeted multi-armed bandits. <NAME>., <NAME>., <NAME>., <NAME>., & <NAME>. (2015).
    """
    
    def __init__(self, nb_arms, posterior):
        self.nb_arms = nb_arms
        self.posterior_means = dict()
        self.posterior_costs = dict()
        for arm in range(self.nb_arms):
            self.posterior_means[arm] = posterior()
            self.posterior_costs[arm] = posterior()

    def start_game(self):
        for arm in range(self.nb_arms):
            self.posterior_means[arm].reset()
            self.posterior_costs[arm].reset()
        
    def choice(self):
        index = [self.posterior_means[arm].sample() / self.posterior_costs[arm].sample() for arm in range(self.nb_arms)]
        return np.random.choice(np.flatnonzero(index == np.amax(index)))
    
    def get_reward(self, arm, reward, cost):
        self.posterior_means[arm].update(reward)
        self.posterior_costs[arm].update(cost)
class TS:
    def __init__(self, nb_arms, posterior):
        self.nb_arms = nb_arms
        self.posterior_means = dict()
        for arm in range(self.nb_arms):
            self.posterior_means[arm] = posterior()

    def start_game(self):
        for arm in range(self.nb_arms):
            self.posterior_means[arm].reset()
        
    def choice(self):
        index = [self.posterior_means[arm].sample() for arm in range(self.nb_arms)]
        return np.random.choice(np.flatnonzero(index == np.amax(index)))
    
    def get_reward(self, arm, reward, cost):
        self.posterior_means[arm].update(reward)
class BGreedy:
    def __init__(self, nb_arms):
        self.nb_arms = nb_arms

    def start_game(self):
        self.t = 1
        self.means = np.zeros(self.nb_arms)
        self.nb_draws = np.zeros(self.nb_arms)
        self.costs = np.zeros(self.nb_arms)
        
    def choice(self):
        if self.t <= self.nb_arms:
            return self.t - 1
        index = self.means / (self.costs + 1e-9)
        return np.random.choice(np.flatnonzero(index == np.amax(index)))
    
    def get_reward(self, arm, reward, cost):
        self.t += 1
        self.means[arm] = ((self.nb_draws[arm] * self.means[arm] + reward) / (self.nb_draws[arm] + 1))
        self.costs[arm] = ((self.nb_draws[arm] * self.costs[arm] + cost) / (self.nb_draws[arm] + 1))
        self.nb_draws[arm] += 1
class BudgetUCB:
    """
        Ref: Budgeted bandit problems with continuous random costs. <NAME>., <NAME>., <NAME>., <NAME>., & <NAME>. (2016).
    """
    
    def __init__(self, nb_arms, lambd=1e-5):
        self.nb_arms = nb_arms
        self.lambd = lambd

    def start_game(self):
        self.t = 1
        self.means = np.zeros(self.nb_arms)
        self.nb_draws = np.zeros(self.nb_arms)
        self.costs = np.zeros(self.nb_arms)
        
    def choice(self):
        if self.t <= self.nb_arms:
            return self.t - 1
        epsilon = np.sqrt(2 * np.log(self.t) / self.nb_draws)
        index = ((self.means + epsilon * 
                  (1 + np.minimum(self.means + epsilon, 1) / np.maximum(self.costs - epsilon, self.lambd))) 
                 / (self.costs + 1e-9))
        return np.random.choice(np.flatnonzero(index == np.amax(index)))
    
    def get_reward(self, arm, reward, cost):
        self.t += 1
        self.means[arm] = ((self.nb_draws[arm] * self.means[arm] + reward) / (self.nb_draws[arm] + 1))
        self.costs[arm] = ((self.nb_draws[arm] * self.costs[arm] + cost) / (self.nb_draws[arm] + 1))
        self.nb_draws[arm] += 1
class UCB:
    def __init__(self, nb_arms):
        self.nb_arms = nb_arms

    def start_game(self):
        self.t = 1
        self.cum_reward = np.zeros(self.nb_arms)
        self.nb_draws = np.zeros(self.nb_arms)
        
    def choice(self):
        if self.t <= self.nb_arms:
            return self.t - 1
        
        index = self.cum_reward / self.nb_draws + np.sqrt(2 * np.log(self.t) / self.nb_draws)
        return np.random.choice(np.flatnonzero(index == np.amax(index)))
    
    def get_reward(self, arm, reward, cost):
        self.t += 1
        self.cum_reward[arm] += reward
        self.nb_draws[arm] += 1<jupyter_output><empty_output><jupyter_text>Experimental setup<jupyter_code>np.random.seed(1234)

nb_rep = 10
scenario = 2

if scenario == 0:
    # Test
    K = 2
    budget = 100
    means = np.array([0.8, 0.5])
    costs = np.array([0.8, 0.15])
    arms = [Bernoulli(means[arm], costs[arm]) for arm in range(K)]
    env = BudgetedMAB(arms, budget)
        
elif scenario == 1:
    # Discrete
    K = 100
    budget = 1000
    means = np.random.random(K)
    costs = np.random.random(K)
    arms = [Bernoulli(means[arm], costs[arm]) for arm in range(K)]
    env = BudgetedMAB(arms, budget)
        
elif scenario == 2:
    # Continuous
    K = 100
    budget = 1000
    rewards_a = 4 * np.random.random(K) + 1
    rewards_b = 4 * np.random.random(K) + 1
    costs_a = 4 * np.random.random(K) + 1
    costs_b = 4 * np.random.random(K) + 1
    arms = [Beta(rewards_a[arm], rewards_b[arm], costs_a[arm], costs_b[arm]) for arm in range(K)]
    env = BudgetedMAB(arms, budget)<jupyter_output><empty_output><jupyter_text>Compare various algorithms<jupyter_code>algorithms = [BTS(K, BetaPosterior),
              BudgetUCB(K),
              BGreedy(K)]
for algo in algorithms:
    print('Start evaluation', algo.__class__.__name__)
    start_time = time.time()
    ev = EvaluationBudgetedMAB(env, algo, nb_rep)
    res, std = ev.mean_regret()
    print('Regret of', algo.__class__.__name__, ': ', res, '+-', std, 
          'obtained in', time.time() - start_time, 'seconds \n')<jupyter_output>Start evaluation BTS
0
1
2
3
4
5
6
7
8
9
Regret of BTS :  1468.2061659380527 +- 72.07326379178045 obtained in 18.376203536987305 seconds 

Start evaluation BudgetUCB
0
1
2
3
4
5
6
7
8
9
Regret of BudgetUCB :  1949.5365984876405 +- 12.776577710054523 obtained in 3.656783103942871 seconds 

Start evaluation BGreedy
0
1
2
3
4
5
6
7
8
9
Regret of BGreedy :  164.59208675114724 +- 171.7471463391528 obtained in 5.681986570358276 seconds
{'fraction_non_alphanumeric': 0.12747964084359992, 'fraction_numerical': 0.028502818960116933, 'mean_word_length': 2.4444444444444446, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '661934', 'license': 'MIT', 'n_tokens_mistral': 3657, 'n_tokens_neox': 3388, 'n_words': 692, 'path': 'budgeted_bandits.ipynb', 'repo_name': 'mjedor/greedy-bandits', 'size': '9584'}