Algorithms and regret bounds for multi-objective contextual bandits with similarity information

Bağlamsal haydut algoritmalarının, bilişsel radyo ağlarından tavsiye sistemlerine ve tıbbi tanıya kadar, belirsiz ortamlarda sıralı karar verme problemlerini çözmede etkili olduğu gösterilmiştir. Bu uygulamaların birçoğu birden fazla ve muhtemelen birbiriyle çelişen amaçlar içerir. Bu tezde, bağlamsal haydut problemlerinin bir uzantısı olan benzerlik bilgisine sahip çok amaçlı bağlamsal haydut problemleri ele alınmıştır. Öğrenicinin seçtiği her kol için rastgele bir skaler ödül aldığı tek amaçlı bağlamsal haydut problemlerinin aksine, çok amaçlı bağlamsal haydut problemlerinde, öğrenici seçtiği her kol için rastgele bir ödül vektörü elde eder. Bu ödül vektörünün her bir elemanı bir amaca karşılık gelir ve ödül vektörünün dağılımı, o turun başlangıcında gözlemlenen bağlama bağlıdır. İlk olarak, bu tezde, bu yapıya uyan, amaçlardan birinin diğer amaca baskın olduğu, iki amaçlı, benzerlik bilgisine sahip yeni bir çok amaçlı bağlamsal haydut problemi tanımlanmıştır. Burada, öğrenicinin amacı, baskın olan amaçtaki toplam ödülünü en üst düzeye çıkardığından emin olmak kaydıyla baskın olmayan amaçtaki toplam ödülünü en üst düzeye çıkarmaktır. Bu problem için bir çok amaçlı bağlamsal haydut algoritması (the multi-objective contextual multi-armed bandit algorithm veya kısaca MOC-MAB) önerilmiştir ve iki farklı performans ölçütü tanımlanmıştır: 2-boyutlu (2D) pişmanlık ve Pareto pişmanlık. Ardından, MOC-MAB'ın hem 2D pişmanlığının hem de Pareto pişmanlığının, tur sayısının altdoğrusal bir fonksiyonu olduğu gösterilmiştir. Ayrıca MOC-MAB'ın sentetik ve gerçek dünya veri kümelerindeki performansı değerlendirilmiştir. Bir sonraki problemde, rastgele sayıda amaca ve benzerlik bilgisine sahip, aynı zamanda yüksek boyutlu ve muhtemelen sayılamayan bir kol kümesi bulunduran çok amaçlı bağlamsal haydut problemi ele alınmıştır. Pareto Contextual Zooming (PCZ) adında bir çevrimiçi öğrenme algoritması önerilmiş ve PCZ'nin Pareto pişmanlığının, tur sayısının altdoğrusal bir fonksiyonu olduğu ve bu fonksiyounun optimuma yakın olduğu gösterilmiştir.