Obliczanie indeksów Gittinsa dla bardziej realistycznych problemów rzadko jest łatwe. Na szczęście ogólne właściwości zaobserwowane w poprzednim podrozdziale – a mianowicie celowość jakiejś kombinacji szacowanej wartości i niepewności – pozwalają na tworzenie prostych polityk, które okazują się „prawie tak dobre” jak polityki optymalne. Pierwsza klasa metod wykorzystuje górną granicę ufności lub heurystykę UCB, wprowadzoną wcześniej dla przeszukiwania drzewa metodą Monte Carlo. Podstawową ideą jest wykorzystanie próbek z każdego ramienia do ustalenia przedziału ufności dla wartości ramienia, to znaczy przedziału, w którym można oszacować, że wartość leży z dużą pewnością; następnie wybierz ramię z najwyższą górną granicą przedziału ufności. Górna granica to bieżące oszacowanie średniej wartości 
plus pewna wielokrotność odchylenia standardowego niepewności tej wartości. Odchylenie standardowe jest proporcjonalne do √1/Ni , gdzie Ni jest liczbą próbkowań ramienia Mi. Mamy więc przybliżoną wartość wskaźnika dla ramienia Mi podaną przez
gdzie g(N) jest odpowiednio dobraną funkcją N, czyli całkowitej liczby próbek pobranych ze wszystkich ramion. Polityka UCB po prostu wybiera ramię o najwyższej wartości UCB. Zauważ, że wartość UCB nie jest ściśle indeksem, ponieważ zależy od N, całkowitej liczby próbek pobranych we wszystkich ramionach, a nie tylko od samego ramienia. Dokładna definicja g określa żal w stosunku do polityki jasnowidzenia, która po prostu wybiera najlepszą rękę i daje średnią nagrodę μ*. Znany wynik Lai i Robbinsa pokazuje, że w przypadku bezdyskontowanym żaden możliwy algorytm nie może żałować, że rośnie wolniej niż O (logN). Kilka różnych opcji g prowadzi do polityki UCB, która odpowiada temu wzrostowi; na przykład możemy użyć g(N) = (2log (1 + N log2N))1/2. Druga metoda, dobór próby Thompsona, wybiera odmianę losowo zgodnie z prawdopodobieństwem, że ta odmiana jest w rzeczywistości optymalna, biorąc pod uwagę dotychczasowe próby. Załóżmy, że Pi(μi) jest bieżącym rozkładem prawdopodobieństwa dla prawdziwej wartości ramienia Mi. Następnie prostym sposobem na zaimplementowanie próbkowania Thompsona jest wygenerowanie jednej próbki z każdego Pi, a następnie wybranie najlepszej próbki. Ten algorytm ma również żal, który rośnie do O (logN).