Mixing
Gittins Index for a simple example
$begingroup$
Everything I can find on the Gittins Index is extremely in depth and abstract with almost no examples. I have spent hours digging through academic papers, lecture notes, and Wikipedia sources. I understand the Gittins Index conceptually, but I would like to include it in program, so I need to know how to compute it (even if the algorithm has a complexity of n factorial).
Is there anyone who can actually solve a simple example like the one below?
This is a version of the classic multi-armed-bandit problem:
I'm at a casino, there are 3 machines M_1, M_2, M_3
Every machine pays out $1 for a win, $0 for a loss
I've played M_1 three times, it has 2 wins 1 loss
I've played M_2 four times, it has 2 wins 2 losses
I've played M_3 two times, it has 1 win 1 loss
If I discount future payouts by 50%;
What is the Gittins Index of M_1?
(An actual number in decimal form)
What steps do you take to get that number?
(Pseudo code would be great)
Thanks for at least reading the problem
decision-theory
asked Oct 15 '17 at 16:02
Jeff HykinJeff Hykin
615
$endgroup$
add a comment |
$begingroup$
Everything I can find on the Gittins Index is extremely in depth and abstract with almost no examples. I have spent hours digging through academic papers, lecture notes, and Wikipedia sources. I understand the Gittins Index conceptually, but I would like to include it in program, so I need to know how to compute it (even if the algorithm has a complexity of n factorial).
Is there anyone who can actually solve a simple example like the one below?
This is a version of the classic multi-armed-bandit problem:
I'm at a casino, there are 3 machines M_1, M_2, M_3
Every machine pays out $1 for a win, $0 for a loss
I've played M_1 three times, it has 2 wins 1 loss
I've played M_2 four times, it has 2 wins 2 losses
I've played M_3 two times, it has 1 win 1 loss
If I discount future payouts by 50%;
What is the Gittins Index of M_1?
(An actual number in decimal form)
What steps do you take to get that number?
(Pseudo code would be great)
Thanks for at least reading the problem
decision-theory
asked Oct 15 '17 at 16:02
Jeff HykinJeff Hykin
615
$endgroup$
$begingroup$
I have now asked my statistics professor, linear algebra professor, theoretical computer science professor, and a computer science faculty member all at Texas A&M and none of them had heard of the Gittins Index.
$endgroup$
– Jeff Hykin
Oct 22 '17 at 20:56
add a comment |
$begingroup$
Everything I can find on the Gittins Index is extremely in depth and abstract with almost no examples. I have spent hours digging through academic papers, lecture notes, and Wikipedia sources. I understand the Gittins Index conceptually, but I would like to include it in program, so I need to know how to compute it (even if the algorithm has a complexity of n factorial).
Is there anyone who can actually solve a simple example like the one below?
This is a version of the classic multi-armed-bandit problem:
I'm at a casino, there are 3 machines M_1, M_2, M_3
Every machine pays out $1 for a win, $0 for a loss
I've played M_1 three times, it has 2 wins 1 loss
I've played M_2 four times, it has 2 wins 2 losses
I've played M_3 two times, it has 1 win 1 loss
If I discount future payouts by 50%;
What is the Gittins Index of M_1?
(An actual number in decimal form)
What steps do you take to get that number?
(Pseudo code would be great)
Thanks for at least reading the problem
decision-theory
asked Oct 15 '17 at 16:02
Jeff HykinJeff Hykin
615
$endgroup$
Everything I can find on the Gittins Index is extremely in depth and abstract with almost no examples. I have spent hours digging through academic papers, lecture notes, and Wikipedia sources. I understand the Gittins Index conceptually, but I would like to include it in program, so I need to know how to compute it (even if the algorithm has a complexity of n factorial).
Is there anyone who can actually solve a simple example like the one below?
This is a version of the classic multi-armed-bandit problem:
I'm at a casino, there are 3 machines M_1, M_2, M_3
Every machine pays out $1 for a win, $0 for a loss
I've played M_1 three times, it has 2 wins 1 loss
I've played M_2 four times, it has 2 wins 2 losses
I've played M_3 two times, it has 1 win 1 loss
If I discount future payouts by 50%;
What is the Gittins Index of M_1?
(An actual number in decimal form)
What steps do you take to get that number?
(Pseudo code would be great)
Thanks for at least reading the problem
decision-theory
decision-theory
asked Oct 15 '17 at 16:02
Jeff HykinJeff Hykin
615
asked Oct 15 '17 at 16:02
Jeff HykinJeff Hykin
615
asked Oct 15 '17 at 16:02
Jeff HykinJeff Hykin
615
asked Oct 15 '17 at 16:02
Jeff HykinJeff Hykin
615
asked Oct 15 '17 at 16:02
Jeff HykinJeff Hykin
615
615
$begingroup$
I have now asked my statistics professor, linear algebra professor, theoretical computer science professor, and a computer science faculty member all at Texas A&M and none of them had heard of the Gittins Index.
$endgroup$
– Jeff Hykin
Oct 22 '17 at 20:56
add a comment |
$begingroup$
I have now asked my statistics professor, linear algebra professor, theoretical computer science professor, and a computer science faculty member all at Texas A&M and none of them had heard of the Gittins Index.
$endgroup$
– Jeff Hykin
Oct 22 '17 at 20:56
$begingroup$
I have now asked my statistics professor, linear algebra professor, theoretical computer science professor, and a computer science faculty member all at Texas A&M and none of them had heard of the Gittins Index.
$endgroup$
– Jeff Hykin
Oct 22 '17 at 20:56
$begingroup$
I have now asked my statistics professor, linear algebra professor, theoretical computer science professor, and a computer science faculty member all at Texas A&M and none of them had heard of the Gittins Index.
$endgroup$
– Jeff Hykin
Oct 22 '17 at 20:56
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Gittins indices are hard to compute. This paper offers a good overview of various algorithms:
http://www.ece.mcgill.ca/~amahaj1/projects/bandits/book/2013-bandit-computations.pdf
answered Jan 7 at 4:10
CarlyleanCarlylean
11
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2473594%2fgittins-index-for-a-simple-example%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Gittins indices are hard to compute. This paper offers a good overview of various algorithms:
http://www.ece.mcgill.ca/~amahaj1/projects/bandits/book/2013-bandit-computations.pdf
answered Jan 7 at 4:10
CarlyleanCarlylean
11
$endgroup$
add a comment |
$begingroup$
Gittins indices are hard to compute. This paper offers a good overview of various algorithms:
http://www.ece.mcgill.ca/~amahaj1/projects/bandits/book/2013-bandit-computations.pdf
answered Jan 7 at 4:10
CarlyleanCarlylean
11
$endgroup$
add a comment |
$begingroup$
Gittins indices are hard to compute. This paper offers a good overview of various algorithms:
http://www.ece.mcgill.ca/~amahaj1/projects/bandits/book/2013-bandit-computations.pdf
answered Jan 7 at 4:10
CarlyleanCarlylean
11
$endgroup$
Gittins indices are hard to compute. This paper offers a good overview of various algorithms:
http://www.ece.mcgill.ca/~amahaj1/projects/bandits/book/2013-bandit-computations.pdf
answered Jan 7 at 4:10
CarlyleanCarlylean
11
answered Jan 7 at 4:10
CarlyleanCarlylean
11
answered Jan 7 at 4:10
CarlyleanCarlylean
11
answered Jan 7 at 4:10
CarlyleanCarlylean
11
11
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2473594%2fgittins-index-for-a-simple-example%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I have now asked my statistics professor, linear algebra professor, theoretical computer science professor, and a computer science faculty member all at Texas A&M and none of them had heard of the Gittins Index.
$endgroup$
– Jeff Hykin
Oct 22 '17 at 20:56