I en multi-armad bandit (MAB) problem, en online-algoritm gör en sekvens av val. I varje omgång väljer man en tidsinvariant uppsättning alternativ och får den utdelning som är förknippad med detta alternativ. Medan fallet med små strategiuppsättningar är nu välförståeligt, har en hel del av det senaste arbetet fokuserat på MAB-problem med exponentiellt eller oändligt stora strategiuppsättningar, där man behöver anta extra struktur för att göra problemet hanterbart. Särskilt den senaste litteraturen behandlade information om likheter mellan armar. Vi anser likhetsinformation i inställningen av kontextuella banditer, en naturlig förlängning av det grundläggande MAB-problemet där före varje omgång en algoritm ges sammanhanget - en antydan om vinsterna i denna omgång. Sammanhangsbanditer är direkt motiverade genom att placera annonser på webbsidor, ett av de avgörande problemen i sponsrad sökning. Ett särskilt enkelt sätt att representera likhetsinformation i kontextuell banditinställning är genom ett likhetsavstånd mellan context-arm-paren, vilket ger en övre gräns för skillnaden mellan respektive förväntad vinst. Tidigare arbete på kontextuella banditer med likhet använder "uniforma" partitioner av likhetsutrymmet, så att i huvudsak varje sammanhang-arm par approximeras av närmaste par i partitionen. Algoritmer baserade på "uniforma" partitioner bortser från strukturen av utbetalningar och kontexten ankomster. Detta är potentiellt slösaktigt, eftersom det kan vara fördelaktigt att upprätthålla en finare uppdelning i högavlönade regioner av likheten utrymme och populära regioner i sammanhanget utrymme. I detta dokument designar vi algoritmer som är baserade på adaptiva partitioner som är anpassade till de populära och hög payoff regioner, och därmed kan dra nytta av problemfall med "benig" utbetalningar eller sammanhang ankomster.
Ett annat relaterat arbete föreslår den kontextuella zoomningsalgoritm REF som klokt partitionerar likhetsutrymmet baserat på belöningsstrukturen i likhetsutrymmet och tidigare sammanhang ankomster.
Contextual Bandits with Similarity Information
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}