Optimizer Methodology

Coframe utilizes a modified Multi-Armed Bandit (MAB) algorithm to dynamically optimize website content. This advanced algorithm enhances traditional MAB strategies by continuously evolving content variants based on performance, ensuring adaptability to user behavior over time.

​

Key Enhancements

1. Dropping Underperforming Arms: Variants that consistently underperform are removed based on dynamic criteria, such as falling below a threshold allocation (e.g., 2% of traffic).
2. Maintaining an Adaptive Holdout Baseline: A control variant is retained for benchmarking, with its traffic allocation gradually reduced to a minimum level (e.g., 5%).
3. Introducing New Arms via AI Conditioning: When a variant is dropped, a new one is generated by an AI model conditioned on the performance of previous variants.
4. Incubation Period for New Arms: New variants are given a protection period (e.g., 5 days) to gather sufficient data before being evaluated for potential removal.

​

Standard Multi-Armed Bandit Overview

In the classical MAB problem, an agent selects among $K$ arms (variants), each with an unknown reward distribution. The objective is to maximize the cumulative reward over time by balancing exploration (trying out less-known arms) and exploitation (selecting the best-known arms).

​

Mathematical Formulation

• Arms: $\mathcal{A} = \{1, 2, \dots, K\}$
• At each time $t$:
  • Select an arm $a_t \in \mathcal{A}$.
  • Receive a reward $r_t$ drawn from the probability distribution associated with $a_t$.

The agent aims to minimize regret $R(T)$, defined as:

where $\mu^*$ is the expected reward of the optimal arm.

In the context of website optimization, regret is closely tied to conversion rate. The regret represents the difference between the cumulative reward (conversions) obtained by always choosing the optimal arm and the actual cumulative reward obtained by the algorithm. A lower regret implies that the algorithm is performing closer to the optimal strategy, which in turn means it’s achieving a higher overall conversion rate. By minimizing regret, the algorithm effectively maximizes the conversion rate over time.

​

Coframe’s Approach

​

Algorithm Steps

​

Initialization

• Initial Set of Arms: $\mathcal{A} = \{0, 1, 2, \dots, K\}$, where $0$ represents the holdout baseline.
• Initial Traffic Allocation: Distribute traffic equally among all arms, i.e., each arm receives $\frac{1}{K+1}$ of the traffic.
• Initial Beta Distribution Parameters: For each arm, initialize with $\alpha = 1$ and $\beta = 20$ for the Beta distribution.
• Iteration Start: The algorithm begins its iterations, with each iteration representing a one-hour time period.

​

At Each Time Step $t$ (Hourly Iteration)

1. Arm Selection:
   • Use a selection policy (Thompson Sampling) to choose an arm $a_t$.
2. Reward Observation:
   • Observe reward $r_t$ ($r_t = 1$ if a conversion occurs, $r_t = 0$ otherwise).
3. Parameter Update:
   • Update the success ($S_i$) and failure ($F_i$) counts for arm $a_t$.

Note on Experimental Unit: Our experimental unit is “unique visitor hours”. Within each one-hour iteration, exposures are deduplicated by visitor using a cookie. This means that the same person within the same iteration will see the same variant/arm, ensuring consistency in the user experience and data collection.

​

Dropping Underperforming Arms

• Criteria for Dropping:
  • An arm is considered for removal if its traffic allocation falls below a predefined threshold (e.g., 2%) and its incubation period has elapsed.
• Rationale:
  • This ensures that resources are focused on more promising variants, improving overall performance.

​

Introducing New Arms

• Generation:
  • For each dropped arm, generate a new variant $v_{\text{new}}$ using an AI model (e.g., a black-box function named ArmGen) conditioned on past data.
• Conditioning Factors:
  • Historical rewards $\{ r_i \}$
  • Content features $\{ v_i \}$
  • The model leverages this information to produce variants with a higher expected reward.

​

Traffic Reallocation

• Adjust Traffic Allocation:
  • Redistribute traffic to include new arms while maintaining minimum allocations for the holdout baseline and ensuring the total allocation sums to 100%.

​

Selection Policy: Thompson Sampling

Thompson Sampling is used for its effective balance between exploration and exploitation.

​

Posterior Sampling

For each arm $i$:

• Successes: $S_i$
• Failures: $F_i$
• Beta Distribution: Sample $\theta_i \sim \text{Beta}(S_i + 1, F_i + 1)$
• Arm Selection: Choose arm $a_t = \arg\max_i \theta_i$

​

Traffic Allocation Constraints

• Minimum Allocation for Holdout Baseline:
  • Ensure the holdout baseline arm $a_0$ retains at least a fraction $\alpha$ of the traffic (e.g., $\alpha = 0.05$).
• Normalization:
  • After reallocation, ensure the total traffic allocation sums to 100%.

​

Advantages Over Standard MAB

1. Continuous Evolution: New variants are regularly introduced, keeping content fresh and aligned with user preferences.
2. Efficient Resource Utilization: Underperforming variants are removed, reallocating resources to better-performing ones.
3. Accelerated Convergence: AI-generated variants, informed by past performance, may lead to higher rewards more quickly.
4. Robust Benchmarking: Maintaining a constant baseline variant allows for consistent performance tracking over time.

​

Mathematical Details

​

Reward Estimation

For each arm $i$:

• Estimated Conversion Rate:

where $n_i = S_i + F_i$ is the total number of times arm $i$ has been selected.

• Credibility Intervals:

Use Bayesian methods to estimate the credibility interval for $\hat{\mu}_i$. This provides a probabilistic range of plausible values for the true conversion rate, given the observed data and prior beliefs.

For each arm $i$, we can calculate the posterior distribution:

where $P(\mu_i)$ is the prior distribution and $P(\text{data} | \mu_i)$ is the likelihood.

The 95% credibility interval can then be derived from the posterior distribution, representing the range within which we believe the true conversion rate lies with 95% probability.

​

Dropping Criterion Justification

• Statistical Significance:

Ensure that enough data has been collected (e.g., minimum sample size $n_{\text{min}}$) before considering an arm for removal.

• Balancing Exploration and Exploitation:

By allowing an incubation period, the algorithm balances the need to explore new variants with the need to exploit known good performers.

​

AI-Conditioned Variant Generation

• Objective:

Generate a new variant $v_{\text{new}}$ expected to have a higher reward than the average of the dropped arms.

• Model Inputs:

  • Features of previous variants $\{ v_i \}$
  • Performance metrics $\{ \hat{\mu}_i \}$

• Model Output:

  • A new variant $v_{\text{new}}$ predicted to perform better.

• Mathematical Formulation:

  • Let the black-box function be ArmGen:

    $$v_{\text{new}} = \text{ArmGen}\left( \{ v_i, \hat{\mu}_i \}_{i \in \mathcal{I}} \right)$$

    where $\mathcal{I}$ is the set of indices of previous arms.

• Expected Reward of New Variant:

  The expected reward of the new variant is:

  $$\mu_{\text{new}} = \mathbb{E}\left[ r_{\text{new}} \mid v_{\text{new}} \right]$$

  Our goal is for $\mu_{\text{new}} > \hat{\mu}_{\text{avg}}$, where $\hat{\mu}_{\text{avg}}$ is the average performance of previous arms.

​

Implementation Considerations

​

Data Sufficiency

• Warm-Up Period:

  Allow new arms to collect sufficient data before making decisions about their performance.

​

Exploration-Exploitation Balance

• Adaptive Parameters:

  Adjust parameters like the minimum allocation and incubation period based on traffic patterns and performance.

​

Computational Efficiency

• Batch Processing:

  Perform updates and evaluations in batches to reduce computational overhead.

​

Comparison with Standard MAB

Aspect	Standard MAB	Coframe’s Modified MAB
Arm Pool	Fixed	Dynamic (arms can be added/dropped)
Underperforming Arms	Continue to receive some traffic	Dropped when below performance thresholds
New Variant Introduction	Not typically included	Introduces new arms via AI conditioning
Baseline Variant	Not necessarily maintained	Constant holdout baseline is maintained
Convergence Speed	Depends on algorithm	Potentially faster due to dynamic updates
Adaptability	Limited to initial arm set	Continuously adapts with new variants

​

Practical Example

Assume we start with:

• Holdout Baseline: $v_0$
• Initial Variants: $v_1$, $v_2$, $v_3$

​

Process Flow

1. Initialization:

   • Equal traffic allocation: each variant receives 25% of traffic.

2. Data Collection:

   • Collect rewards over time for each variant.

3. Evaluation:

   • After sufficient data, suppose $v_2$ falls below the 2% allocation threshold.

4. Dropping Underperformer:

   • Drop $v_2$ from the active arm set.

5. Variant Generation:

   • Generate a new variant $v_{\text{new}}$ using the ArmGen model conditioned on past variants and their performance.

6. Reallocation:

   • Redistribute traffic among $v_0$, $v_1$, $v_3$, and $v_{\text{new}}$.

7. Iteration:

   • Repeat the process, continuously refining the variant pool.

​

Conclusion

Coframe’s modified multi-armed bandit algorithm offers a robust and efficient method for website content optimization by:

• Leveraging Past Performance: AI-generated variants are informed by historical data, increasing the likelihood of success.
• Dynamic Adaptation: The ability to drop and introduce arms keeps the optimization process responsive to changing user behaviors.
• Maintaining a Baseline: A constant control variant ensures that performance improvements are measured accurately.

This approach outperforms standard MAB algorithms by providing a mechanism for continuous improvement and faster convergence toward optimal content configurations.

​

Postscript: For Math Nerds

Let’s provide a rigorous mathematical argument to demonstrate why a dynamic multi-armed bandit (MAB) with an infinite universe of arms—where arms are dynamically introduced and dropped based on performance—is superior to a traditional A/B/n test or a fixed MAB with $K$ variants.

​

Problem Setup

​

Infinite-Armed Bandit Model

• Arm Universe: An infinite set of arms $\mathcal{A} = \{a_1, a_2, a_3, \dots\}$.
• Reward Distributions: Each arm $a \in \mathcal{A}$ is associated with an unknown reward distribution $R_a$, with expected reward $\mu_a$.
• Active Arms: At any time $t$, only a subset $\mathcal{S}_t \subset \mathcal{A}$ with $|\mathcal{S}_t| = K$ arms is actively being considered.
• Arm Replacement Mechanism:
  • Dropping Arms: An arm $a \in \mathcal{S}_t$ is dropped if its allocation falls below a threshold $\theta$.
  • Introducing New Arms: A new arm $a_{\text{new}}$ is introduced using a function (e.g., ArmGen) based on information from existing arms, aiming to select arms with potentially higher expected rewards.

​

Traditional Fixed MAB Model

• Fixed Arms: A static set of $K$ arms $\mathcal{F} = \{a_1, a_2, \dots, a_K\}$ used throughout the time horizon.
• Reward Distributions: Each arm $a \in \mathcal{F}$ has an unknown reward distribution $R_a$, with expected reward $\mu_a$.
• No Replacement: Arms are neither dropped nor added; the set $\mathcal{F}$ remains constant.

​

Objective

Maximize the cumulative expected reward over a time horizon $T$:

where $r_t$ is the reward obtained at time $t$.

​

Performance Metric

• Regret:

where $\mu^* = \sup_{a \in \mathcal{A}} \mu_a$ is the maximum expected reward among all arms.

Our goal is to show that the dynamic MAB has a lower regret than the traditional fixed MAB.

​

Mathematical Argument

​

Assumptions

1. Bounded Rewards:

   • Rewards are bounded in $[0,1]$.

2. Correlation via Feature Space:

   • Arms can be represented in a feature space $\mathcal{X}$, and similar features imply similar expected rewards.

3. Existence of Better Arms:

   • The arm set $\mathcal{A}$ contains arms with expected rewards approaching $\mu^*$.

​

Analysis of the Fixed MAB

• Limitation:

  • The best expected reward achievable is $\mu_{\max}^{\mathcal{F}} = \max_{a \in \mathcal{F}} \mu_a$.

  • Regret is:

    $$R_T^{\text{fixed}} = T (\mu^* - \mu_{\max}^{\mathcal{F}}).$$

• Observation:

  • If $\mu_{\max}^{\mathcal{F}} < \mu^*$, the regret grows linearly with $T$.

​

Analysis of the Dynamic MAB

• Adaptive Exploration:

  • By introducing new arms based on learned information, the dynamic MAB can discover arms with higher expected rewards over time.

• Regret Decomposition:

  • Regret can be bounded as:

    $$R_T^{\text{dynamic}} \leq C \left( \sum_{a \in \mathcal{A}} \frac{\log T}{\Delta_a} \right),$$

    where $\Delta_a = \mu^* - \mu_a$ and $C$ is a constant.

• Sublinear Regret:

  • The dynamic MAB achieves sublinear regret growth, i.e., $R_T^{\text{dynamic}} = o(T)$.

​

Comparing Regrets

• Fixed MAB:

  • Regret is linear in $T$ if $\mu_{\max}^{\mathcal{F}} < \mu^*$.

• Dynamic MAB:

  • Regret grows sublinearly with $T$ due to the exploration of new, potentially better arms.

• Conclusion:

  • As $T \to \infty$, the average regret per time step for the dynamic MAB approaches zero, while it remains constant for the fixed MAB.

​

Formal Proposition

Proposition: In an infinite-armed bandit problem where expected rewards are correlated through observable features, a dynamic MAB algorithm that introduces new arms based on these features and replaces underperforming arms achieves lower cumulative regret than a traditional fixed MAB with a static set of arms.

Proof Sketch:

1. Potential for Improvement:

   • The dynamic MAB can discover arms with expected rewards closer to $\mu^*$ over time.

2. Efficient Exploration:

   • By leveraging the feature space, the algorithm focuses exploration on promising regions.

3. Regret Bounds:

   • Utilizing algorithms designed for structured bandits (e.g., contextual MAB algorithms), the regret can be bounded sublinearly.

4. Asymptotic Superiority:

   • Over a long time horizon, the dynamic MAB’s cumulative regret grows slower than that of the fixed MAB.

​

Mathematical Details

​

Regret Bounds in Structured Bandits

• Lipschitz Continuity:

  • If the expected reward function $\mu(a)$ is Lipschitz continuous over the feature space $\mathcal{X}$:

    $$|\mu(a) - \mu(b)| \leq L \| x_a - x_b \|,$$

    where $L$ is the Lipschitz constant.

• Algorithm Performance:

  • Algorithms like the Zooming Algorithm achieve regret bounds of:

    $$R_T = O\left( T^{(d+1)/(d+2)} (\log T)^{(d+1)/(d+2)} \right),$$

    where $d$ is the dimension of the feature space.

​

Implications

• Sublinear Growth:

  • The dynamic MAB’s regret grows slower than any linear function of $T$.

• Adaptability:

  • The ability to introduce new arms allows the algorithm to adapt to the best-performing regions in the feature space.

​

Conclusion

By rigorously analyzing regret bounds and leveraging the structure of the infinite arm space, we demonstrate mathematically why the dynamic MAB outperforms the traditional fixed MAB in maximizing cumulative expected reward over time.

​

References

• Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-Time Analysis of the Multiarmed Bandit Problem. Machine Learning.
• Kleinberg, R., & Slivkins, A. (2010). Multi-Armed Bandits in Metric Spaces. Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC).
• Bubeck, S., Munos, R., & Stoltz, G. (2011). Pure Exploration in Finitely-Armed and Continuous-Armed Bandits. Theoretical Computer Science.