Multi Armed Bandit

2026-01-18 · 3 min read

Multi-Armed Bandit (yazının devamında kısaca MAB diyeceğim) problemi, belirsizlik altında karar verme, öğrenme ve optimizasyon konularının merkezinde yer alan klasik bir pekiştirmeli öğrenme problemidir. Adını, her kolu farklı ve bilinmeyen ödül dağılımına sahip olan slot makinelerinden alır. Amaç, zaman içinde hangi kolun seçileceğini öğrenerek toplam beklenen ödülü maksimize etmektir. Bu problem, keşif (exploration) ve kullanım (exploitation) arasındaki dengeyi ele alır.

MAB problemi, reklam tıklamaları, klinik deneyler gibi bir çok gerçek uygulamada karşımıza çıkar.

MAB probleminde seçilen aksiyonlar ortamın durumunu (ödül dağılımını) değiştirmez! Bu nedenle MAB, pekiştirmeli öğrenmenin en sade ve özel durumu olarak düşünülebilir.

Matematiksel İfade

Bir MAB problemi aşağıdaki bileşenlerden oluşur:

• Kollar (Arms): $K$ adet eylem vardır ve bu eylemlerin her birinin ödül dağılımı farklıdır.

• Ödül (Reward): Seçilen kol, rastgele bir ödül üretir:

$$r_t\sim D_i$$

Burada $D_i$, $i$. kolun bilinmeyen ödül dağılımıdır.

• Zaman: Kararlar sıralı olarak verilir, $t=1,2,\ldots,T$.

Herhangi bir $t$ anında, sadece seçilen kola ilişkin ödül gözlemlenir, diğer kollar hakkında bilgi edinilemez.

MAB probleminin amacı, toplam beklenen ödülü maksimize etmektir:

$$\max \mathbb{E}\left[\sum_{t=1}^{T} r_t \right]$$

Bandit algoritmalarının performansı regret (algoirtmanın, ideal stratejiye göre ne kadar kaybettiği) ile ölçülür:

$$R_T=T\mu^\star-\mathbb{E}\left[\sum_{t=1}^Tr_t\right]$$

Burada, $\mu^\star$ en iyi kolun beklenen ödülüdür. Amaç $R_T$ 'yi sub-linear yapmaktır. Bu sayede algoritma zaman ilerledikçe optimale yakın davranmaya başlar.

Politikalar

Epsilon-Greedy ( $\epsilon$ - greedy)

Her bir adımda

• $\epsilon$ olasılıkla rastgele bir kol seçerek keşif yapar;
• $1-\epsilon$ olasılıkla o ana kadar en yüksek ortalama ödüle sahip kolu seçer.

Basit ve etkili bir algoritma olmasına rağmen, $\epsilon$ sabit olduğundan zamanla daha az keşif yapılmasını sağlamaz; kötü kolları halen denemeye devam edebilir.

Softmax

Kolların seçilme olasılıklarını sıcaklık (temperature) parametresiyle normalize eder:

$$P(i)=\frac{e^{\frac{\hat{\mu_i}}{\tau}}}{\sum_j je^{\frac{\hat{\mu_j}}{\tau}}}$$

Bu sayede iyi kollara odaklanırken düşük ödüllü kollara da şans verir.

Upper Confidence Bound (UCB)

Her bir kolun ortalama ödülüne bir güven sınırı ekler ve en yüksek üst sınıra sahip kolu seçer. Az denenmiş kolların güven sınırları daha büyük olacağından doğal olarak keşif imkanı sağlar:

$$\text{UCB}_i(t)=\hat{\mu}_i+\sqrt{\frac{2\ln t}{N_i}}$$

Thompson Sampling

Her bir kol için tek bir ortalama değer tutmak yerine ödül dağılımını tutar ve her adımda bu dağılımdan örneklem yapar ve en yüksek değere sahip kolu seçer.

MAB probleminin Daha Genel Halleri

Klasik MAB probleminde her kolun ödül dağılımı sabit ve zamandan bağımsızdır. Ancak gerçek dünyada bu varsayım çoğu zaman geçerli değildir. Bu nedenle literatürde MAB’nin daha genel ve güçlü iki önemli uzantısı geliştirilmiştir: Contextual Bandits ve Adversarial Bandits.

Contextual Bandits

Contextual Bandit problemlerinde, her karar anında ortama dair ek bilgi (bağlam - context) gözlemlenir. Politika bağlama bağlı olarak bir aksiyon seçer. LinUCB algoritması bu tür bir algoritmadır.

Adversarial Bandits

Adversarial Bandit problemlerinde ödüller sabit bir olasılık dağılımından gelmez. Aksine, ortam "kötü niyetli" bir rakip gibi davranarak ödülleri algoritmayı yanıltacak veya en kötü duruma (worst-case) düşürecek şekilde belirleyebilir. Bu nedenle klasik olasılıksal varsayımlar yapılamaz. Algoritmanın performansı, geriye dönük olarak her zaman en iyi kolu seçen bir stratejiye kıyasla ölçülür (Pişmanlık - Regret minimizasyonu). EXP3 algoritması bu tür bir algoritmadır.

Kaynaklar

• Pekiştirmeli Öğrenme (Reinforcement Learning)'e Giriş ve Temel Kavramlar
• https://github.com/mrtkp9993/mab-example