Çok Silahlı Haydutlar: Göreviniz için En İyi Takviyeli Öğrenme Çözümü

Çok Silahlı Haydutlar (MAB'ler), Takviyeli Öğrenme dünyasında bir temel taşı oluşturur ve keşif ile kullanım arasında en uygun dengeyi gerektiren senaryoları müzakere etmek için güçlü bir mekanizma sunar. Keşif, yeni seçenekleri denemek anlamına gelirken, faydalanma mevcut en iyi seçeneğe bağlı kalmayı ifade eder. Bu gibi durumlarda, MAB'lerin akıllı öğrenme mekanizmaları nedeniyle sıklıkla mükemmel bir seçim olduğu kanıtlanır.

İlk önce MAB'lerin arkasındaki konsepti çözelim. Her biri "tek kollu haydut" olarak bilinen bir dizi slot makinesiyle çevrili bir kumarbaz düşünün. Burada verilecek kritik kararlar hangi makinelerde oynanacağını, oynama sırasını ve oyun sıklığını belirlemeyi içerir. İşin püf noktası, her makinenin farklı, belirsiz bir ödül sunmasıdır. Nihai amaç, bir dizi oyun boyunca en yüksek kümülatif ödülü toplamaktır.

Çok Silahlı Haydut Nedir?

"Çok kollu haydut" adı, bir dizi kumar makinesinde (genellikle "tek kollu haydutlar" olarak bilinir) bir kumarbazın yer aldığı bir düşünce deneyinden gelir. Kumarbazın, toplam ödülünü en üst düzeye çıkarmak amacıyla hangi makinelerde oynayacağına, her makineyi kaç kez ve hangi sırayla oynayacağına karar vermesi gerekir.

Daha resmi bir tanımla, bir MAB problemi bir demettir (A, R)

MAB problemindeki amaç, belirli bir tur sayısı boyunca beklenen toplam ödül Q maksimuma çıkaran bir π politikası (geçmiş verilerden eylemlere bir haritalama) bulmaktır.

MAB'daki temel ikilem, "keşif" ile "sömürü" arasındaki dengedir:

1. Keşif, getirebilecekleri ödül hakkında daha fazla bilgi edinmek için farklı kolları denemeyi içerir. Bu, optimal olmayan kolların çekilmesini gerektirebilir, ancak sistem hakkında bilgi toplanmasına yardımcı olur.
2. Sömürü , şu ana kadar topladığı bilgilere dayanarak, ajanın şu anda beklenen en yüksek ödülü alacağına inandığı kolun çekilmesini içerir.

Keşif ve kullanım arasında denge kurmak, takviyeli öğrenme ve MAB problemlerinde temel bir zorluktur.

Bu sorunu çözmek için Epsilon-Greedy, Upper Confidence Bound (UCB) ve Thompson Örnekleme stratejileri dahil olmak üzere bir dizi algoritma geliştirilmiştir.

MAB'ın bir uzantısı olarak Bağlamsal Haydutların ayrıntılı incelemesi sonraki makalelerde ele alınacaktır.

Epsilon(ε)-Açgözlü

Epsilon(ε)-Greedy stratejisi basit bir prensibe bağlıdır. Çoğu zaman (1 - ε) olarak ölçülen, en yüksek tahmini ödülü veren eylemi tercih eder, böylece en iyi bilinen seçeneği kullanır. Ancak, ε olarak ölçülen zamanın geri kalanında rastgele bir eylem seçer ve böylece yeni olasılıkları keşfeder. Bu stratejinin yaratıcılığı, keşif aşamasında en ödüllendirici eylemlerle aynı olasılıkla daha az ödüllendirici eylemleri seçebileceği ve ε değerinin keşif ve kullanım arasındaki dengeyi belirlediği uyarısına rağmen basitliği ve etkililiğinde yatmaktadır.

Matematiksel olarak şu şekilde tanımlanabilir:

Bu, aşağıdaki sözde kodla tanımlanabilir:

 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

Epsilon-Greedy stratejisinin Pythonic uygulaması oldukça basittir:

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) else: return np.argmax(self.values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

ε-açgözlü algoritma basitlik avantajına sahiptir ve birçok adımdan sonra bile (biraz) keşfetmeye devam edeceğini garanti eder. Ancak, UCB veya Thompson Sampling'in aksine, araştırma yaparken her bir eylem hakkında ne kadar bilindiğini hesaba katmaz.

UCB

Tersine, UCB stratejisi, bir eyleme karar verirken hem tahmini ödülü hem de ilgili belirsizliği veya farklılığı hesaba katar. Belirsizliğin yüksek olduğu eylemleri tercih ederek bunu azaltmaya çalışır ve daha verimli bir keşif aşaması sağlar. UCB stratejisi matematiksel olarak şu şekilde tanımlanır:

Python uygulaması aşağıdaki gibidir:

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(ucb_values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

UCB'de keşif ve kullanım arasındaki denge, formülünden gelir: bir eylemin tahmini değeri artı zaman içinde azalan (eylem hakkında daha fazla şey öğrenildikçe) ancak o eylem hakkındaki belirsizlikle birlikte artan bir terim. Bu nedenle algoritma, belirsizliği yüksek ve ödül potansiyeli yüksek olan silahları keşfetme eğilimindedir.

Thompson Örneklemesi

Thompson Sampling, çok kollu haydut sorunu için Bayes'ten ilham alan bir algoritmadır. Her haydutun (veya her eylemin) ödül olasılıklarına bir ön dağılım atar ve ardından ödüller gözlemlendikçe bu öncelikleri günceller. Eylem seçimi, en iyi eylem üzerindeki sonsal dağılıma göre olasılıksaldır.

Beta-Bernoulli çerçevesinde, her haydutun ödül dağılımını bir Bernoulli dağılımı olarak ele alıyoruz (yani ikili ödüller 0 veya 1). Daha sonra ödül alma olasılığından önce bir Beta atarız. Beta dağılımı, Bernoulli dağılımının önceki eşleniğidir ve bu, kolay bir son güncellemeye olanak tanır.

Mantık:

1. Her hayduta α=1, β=1 (Önceki tek tip) parametrelerini içeren bir Beta dağılımı atayın.

2. Her tur için:

   1. Her haydutun mevcut Beta dağılımından rastgele bir sayı örnekleyin.
   2. En yüksek sample sayısına sahip haydutu seçin ve o haydutu çekin.
   3. Çekilmiş haydutun ödülünü gözlemleyin. Başarılı olursa (1), haydutun α'sını bir artırın; eğer başarısızlık (0) ise, haydutun β'sını bir artırın.
   4. 2. ve 3. adımları tekrarlayın.

 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

Dolayısıyla Thompson Sampling, hakkında belirsiz olduğu eylemleri (değer dağılımının yayılmış olduğu eylemleri) "keşfeder" ve yüksek değere sahip olabileceğine inandığı eylemleri (dağılımı yüksek değerlere doğru çarpık olanlar) "istismar eder".

Zamanla, her bir eylem hakkında daha fazla şey öğrenildikçe, dağılımlar daha da zirveye ulaşır ve algoritma tarafından seçilen eylemler, en yüksek beklenen değere sahip olana yaklaşma eğilimi gösterir.

Thompson Örneklemesindeki keşif/kullanım dengesi doğal olarak dağılımların şeklinden gelir. Bu yöntem oldukça etkilidir ancak özellikle büyük veya sürekli eylem alanları veya karmaşık ödül yapılarıyla ilgili problemlerde uygulanması UCB veya ε-açgözlülüğe göre daha karmaşık olabilir.

Neden Çok Silahlı Haydutlar Göreviniz için En İyi RL'dir?

1. Basitlik : MAB algoritmaları, potansiyel olarak büyük bir durum-eylem değeri tablosunun veya yaklaşımının sürdürülmesini ve güncellenmesini gerektiren tam teşekküllü RL algoritmalarından daha basit ve hesaplama açısından daha verimlidir.
2. Keşif ve kullanım dengesi : MAB algoritmaları, yeni eylemleri denemek ile bilinen iyi eylemlere bağlı kalmak arasındaki dengeyi yönetmek için sağlam yöntemler sağlar.
3. Gerçek zamanlı uyarlanabilirlik : MAB algoritmaları, eylemlerin ödül dağılımlarındaki değişikliklere gerçek zamanlı olarak uyum sağlayabilir.
4. Kolay entegrasyon : MAB'lerin basitliği ve verimliliği, mevcut sistemlere kolay entegrasyona olanak tanır ve minimum kesintiyle anında fayda sağlar.
5. Geniş uygulanabilirlik : MAB'ler, reklamcılık (tıklama oranını en üst düzeye çıkarmak için hangi reklamın gösterileceğinin seçilmesi), sağlık hizmetleri (tedavi stratejilerinin kişiselleştirilmesi) ve web sayfası optimizasyonu (A/B testi) dahil olmak üzere çeşitli alanlarda başarıyla uygulanmıştır.

MAB'lerin uygulamaları

Çok Silahlı Haydutlar (MAB'ler), çeşitli endüstriler ve alanlarda geniş bir uygulama yelpazesine sahiptir. İşte bunların nasıl kullanılabileceğine dair bazı örnekler:

1. Çevrimiçi Reklamcılık : MAB'ler, etkileşimlerine göre kullanıcılara gösterilecek reklamların seçimini dinamik olarak ayarlamak için kullanılabilir. Bu, zaman içinde tıklama oranlarını veya dönüşümleri en üst düzeye çıkarmaya yardımcı olur.
2. Klinik Araştırmalar : Tıbbi araştırmalarda, MAB algoritmaları hastaları dinamik olarak farklı tedavilere atamak için kullanılabilir. Bu, daha fazla hastanın en etkili tedavileri almasını sağlayarak pişmanlığın, yani her zaman en iyi tedaviyi seçememekten kaynaklanan kaybın azalmasını sağlar.
3. Haber Makalesi Önerisi : Haber siteleri, her kullanıcıya gösterilen makaleleri kişiselleştirmek için MAB'leri kullanabilir. MAB algoritması zamanla her kullanıcının hangi tür makalelerle ilgilendiğini öğrenebilir ve önerileri buna göre ayarlayabilir.
4. Dinamik Fiyatlandırma : E-ticaret platformları veya havayolları, fiyatlandırma stratejilerini gerçek zamanlı olarak optimize etmek ve müşteri davranışına ve pazar dinamiklerine göre geliri en üst düzeye çıkarmak için MAB algoritmalarını kullanabilir.
5. Ağ Yönlendirme : Bilgisayar ağlarında, tıkanıklığı yönetmek ve paketlerin yönlendirilmesini optimize etmek için MAB algoritmaları kullanılabilir. Her rota bir kol olarak ele alınabilir ve algoritma, paket kaybını veya gecikmeyi en aza indirmek için rotaları dinamik olarak seçebilir.
6. Makine Öğrenimi Hiperparametre Ayarlama : MAB'ler, makine öğrenimi modellerinde hiper parametrelerin seçimini optimize etmek için de kullanılabilir. Her bir hiperparametre seti bir kol olarak ele alınabilir ve algoritma, optimum model konfigürasyonunu bulmak için seçimi yinelemeli olarak hassaslaştırabilir.

Temelde, MAB'lerin faydası geleneksel takviyeli öğrenme görevlerinin çok ötesine uzanır. Belirsizlik ortamlarında karar verme süreçlerini geliştirmek ve çeşitli alanlardaki gerçek dünya sorunlarına pratik çözümler sunmak için etkili bir çerçeveyi sembolize ediyorlar. Bu nedenle, eldeki görev keşif ve kullanım arasında denge kurmayı gerektirdiğinde, MAB'ler sıklıkla tercih edilen seçenek olarak ortaya çıkıyor ve karar vermedeki bilmecelere çok yönlü, sağlam ve uyarlanabilir bir çözüm sunuyor.

Çözüm

Çok Silahlı Haydutlar, keşif ve sömürüyü etkili bir şekilde dengeleme yetenekleriyle, gerçek dünyadaki birçok karar verme sorununa sağlam bir çözüm sunar. İçsel uyarlanabilirlikleri ve çok yönlülükleri, onları yalnızca pekiştirmeli öğrenme alanında değil, aynı zamanda sağlık hizmetlerinden çevrimiçi reklamcılığa kadar geniş bir uygulama yelpazesinde değerli bir araç haline getiriyor. İster bir veri bilimcisi, ister makine öğrenimi meraklısı olun, ister karar verme süreçlerinizi geliştirmek isteyen bir profesyonel olun, MAB stratejilerini anlamak ve uygulamak, zenginleştirici ve ödüllendirici bir deneyim olabilir.