<p>(This is an attempt to reformulate <a href="https://stackoverflow.com/questions/11941402/ultimate-jedi-challenge-multiarmed-bandit-reinforcement-learing-advanced-ai">this question</a> more concisely.)</p>

<h2>Context</h2>

<p>You are a Jedi master who wants to prepare a training program (online-algorithm) for his apprentice, "Luke". Luke needs to practice several (10-20) <em>abilities</em>. You can train Luke by preparing <em>challenges</em>, each connected to one <em>ability</em>.</p>

<p>The outcome of each challenge is binary: Luke succeeds (1) or Luke fails (0). If Luke fails a challenge in an ability, you give him a <em>lecture</em> that you can assume will improve his chance of succeeding in next challenge in this ability.</p>

<p>You have a limited number (~50) of challenges to use before Luke has to take a test. However, if Luke fails at some challenge during practice you receive extra challenges. The goal of your training program is to maximize the outcome of the <em>test</em>. The <em>test</em> is a set of (about 20-25) challenges uniformly distributed between abilities.</p>

<h2>Problem definition</h2>

<p>Consider a problem of probing a set $P = \{p_0,...,p_n\}$ of $N$ independent processes which resemble human learning (practice makes perfect). At each time the program chooses one process $i$ to probe, denoted by the action $U(t)$, and receives an information of the current, <strong>binary</strong> state $S_i(t)$ of that process. The probability of $S_i(t)$ = 1 is defined by 
$$
 p(S_i(t) = 1) = g_i(c_i(t))
$$
 Where $g_i$ is a non-decreasing function and $c_i(t)$ describes how many times proces $p_i$ was probed so far. We can assume $g_i$ ressembles the <strong>learning curve</strong>, but each $g_i$ can have an arbitraty offset at $t_0$ ie:
<img src="https://i.sstatic.net/W0u5t.png" alt="$g_i$ offset on the learning curve at time $t_0$">
 Knowing that the amount of remaining probing action is given by
$$
h(t+1) = \begin{cases}
            h(t)-1\,, &amp;\text{ if $i \in U(t)$ and $S_i(t) = 1$;} \\
            h(t)-1+f(h(t))\,, &amp;\text{ otherwise,}
\end{cases}
$$
where the function $f$ is one of the input variables &mdash; propose a <em>probing policy</em> which maximizes a testing function $q$ that will evaluate the state of all processes when there are no more remaining probes, namely:
$$q(t_{stop}) = \sum_{i = 0}^{N}S_i(t_{stop}),$$
where $t_{stop}$ is such that $h(t_{stop}) = 0$.</p>

<h2>My ideas of approaching this problem</h2>

<p>We can try to model this problem in at least two ways:</p>

<ol>
<li><p>As a special case of Non-Bayesian Binary Restless Multi-armed Bandit (RMBA) with Non-Identical Arms (some reading <a href="http://arxiv.org/abs/1011.4752" rel="nofollow noreferrer">one</a>, <a href="http://www-scf.usc.edu/~ygai/papers/Allerton2011.pdf" rel="nofollow noreferrer">two</a>, <a href="http://www.isif.org/sites/isif.org/files/journals/2-6075D01.pdf" rel="nofollow noreferrer">three</a>) meaning :</p>

<ul>
<li>Restless - reward probability evolves over time </li>
<li>Non-Bayesian - underlying Markov transitions are not known</li>
<li>Non-Identical Arms - each arm is an independent Markov process </li>
<li>We would assume that the algorithm receives a reward each time it probes a process that will return 0 (Luke fails a challenge). </li>
<li>I would start by adopting some policy similar to $\epsilon$-greedy.</li>
</ul></li>
<li><p>As a case for Reinforcement Learning .</p>

<ul>
<li>I'm just starting to familiarize myself with these areas of research so I can't provide any insight here, although according to my initial reading it seems very promising. I will update the question once I learn anything meaningful.</li>
</ul></li>
</ol>

<h2>Question</h2>

<p>What would you recommend as the best references for this problem, or closely related problems? I'm interested primarily in approaches which are not just theoretically feasible, but which would be effective in practise.</p>

<p>Can you suggest a policy that would be effective with these constraints? I am especially interested in good ways to update the belief vector.</p>

CC BY-SA 3.0
2012-08-15T17:47:35.957Z
I appreciate the edits improving question quality. I do not appreciate changing the title - its purpose is to attract attention and set up the context.
JohnnyM
CC BY-SA 3.0
2012-08-15T18:03:01.637Z
You forgot to specify how S_i(t) is defined.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-15T18:45:52.657Z
@TsuyoshiIto Done! It was stated in the context but I added it to the technical definition.
JohnnyM
CC BY-SA 3.0
2012-08-15T19:19:35.757Z
As a general issue, you should understand that what you need is not a “problem definition in technical terms,” but a precise definition.  Of course, to state a precise definition, you usually need some technical terms, but using technical terms is not a goal.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-15T19:19:55.957Z
As a specific issue, specifying that S_i(t) is binary does not define what the value of S_i(t) is: it only says that it is either 0 or 1.  If it is chosen randomly, you have to specify the probability distribution.  If it is chosen adversarially, you have to specify what the constraint on the choice is.  With the current formulation, I cannot rule out the possibility that no matter what I do, I receive S_1(t_stop) = … = S_n(t_stop) = 0, completely unrelated to the values of S_i(t) for t<t_stop.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-15T23:55:36.850Z
@Johnny, I think your title is more like keywords and doesn't state your question. The general advice is to make your question the title. I suggest using the tags in place of the title for listing keywords. (Or you can list them inside the question.)
Kaveh
CC BY-SA 3.0
2012-08-16T10:29:28.173Z
@TsuyoshiIto Thank you for this insight - in general the process should model human learning and it's hard to define it. In simple words you wan't to probe it (train it) enough times for it to start returning 1's. I do have an idea of how to present it but it needs some refinement. I will post it in the afternoon.
JohnnyM
CC BY-SA 3.0
2012-08-16T12:10:39.187Z
When revising the question, please also check the following page, which contains useful advice from many people on asking questions about how to model something: http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions.  Such questions can become great questions which connect theoretical computer science to other fields.  But in its current form, I am afraid that your question is an example of the bad scenario which Scott described: _if the only answer to your question you could reasonably expect from a TCS expert is "I dunno," why are you asking it here? :)_
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-17T01:46:41.453Z
I suppose, as a first approximation, $S_i(t)$ is a bernoulli random variable s.t. the  probability of getting one is a function of the number "probes". I.e. we can think of $p_i:\mathbb{N} \rightarrow [0, 1]$, which is a decreasing function, and when $i$ has been probed $x = x_i(t)$ times up to step $t$, $S_i(t) = 1$ w.p. $p_i(x)$. Is this fair?
Sasho Nikolov
CC BY-SA 3.0
2012-08-17T13:01:40.780Z
FYI, this question was also crossposted at http://stats.stackexchange.com/questions/34371.
whuber
CC BY-SA 3.0
2012-08-17T19:05:33.047Z
@SashoNikolov Yes this seems fair - this is more or less how I was going to describe it! I know I said I will update the question yesterday but my professional duties overwhelmed me in last 2 days. I will extend the question to include a modified version of your proposal tommorow.
JohnnyM
CC BY-SA 3.0
2012-08-18T22:21:15.787Z
@Sasho: Why is p_i a decreasing function?  I thought that it should be an increasing function.  (Not that I care much about this question, especially after seeing whuber’s link.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-19T09:51:02.167Z
@TsuyoshiIto sure, increasing. i was thinking of $S_i(t)$ as an error indicator, but I guess it's a success indicator. i think it's a potentially interesting  question (but have not thought about it much to make sure it's not trivial or ill-defined) that's not written in the best way. why does whuber's link change anything? crossposting is orthogonal to question quality imo
Sasho Nikolov
CC BY-SA 3.0
2012-08-19T23:06:40.357Z
@SashoNikolov We can view it both ways - to be honest it does not change much in my opinion. Also, could you suggest ways to improve this question? I did my best and based the description on common descriptions of Multiarmed Bandit (see references). I will appreciate all comments that will lead to improving this quest. I also have no idea why Tsuyoshi Ito thinks crossposting  changes anyting - this question falls into scope of both sites and they do have different readership.
JohnnyM
CC BY-SA 3.0
2012-08-20T01:15:52.567Z
@JohnnyM you have not edited the question to make precise how the distribution of $S_i$ changes with the number of probes (i.e. incorporate my suggestion above or something else). Also, crossposting is discouraged on stachexchange, so please close one of your questions and you can reopen it if the other one yields no answers. I was just saying that crossposting is orthogonal to question quality, but I am not encouraging it!
Sasho Nikolov
CC BY-SA 3.0
2012-08-21T03:55:50.153Z
I would like to know why hell did not break loose because this person submitted an extremely similar question after this one got 6 minus votes http://cstheory.stackexchange.com/questions/12290/ultimate-jedi-challenge-multiarmed-bandit-reinforcement-learing-advanced-ai
Tayfun Pay
CC BY-SA 3.0
2012-08-21T03:56:47.920Z
So are we picking and choosing who can re-post a question after it gets so any negative votes instead of encouraging them to revise the first question?
Tayfun Pay
CC BY-SA 3.0
2012-08-21T09:29:18.967Z
@SashoNikolov I've updated the question with the definition of $S_i$ and an initial model of how the probability of $S_i = 1$ is changing overtime. I would appreciate a quick guide how to close the crossposted question - there is nothing in the faq.
JohnnyM
CC BY-SA 3.0
2012-08-21T09:33:05.560Z
@Geekster I'll let you know this new question has very little to do with the previous post this is more narrowed down, precise and well defined - if one can publish 2 articles one specific and another with a more broad approach I don't see why the same principle cannot apply to cstheory questions.
JohnnyM
CC BY-SA 3.0
2012-08-21T13:43:28.233Z
@Geekster: Hell did not break loose because of the obvious _effort_ the OP put into reformulating his question.  It wasn't just a verbatim repost.
Jeffε
CC BY-SA 3.0
2012-08-21T13:45:02.350Z
@JohnnyM: If you can't close the cross-posted question on stats.SE yourself, flag the question and ask the moderators to close it.  (Also: Don't do that again.)
Jeffε
CC BY-SA 3.0
2012-08-21T14:43:04.683Z
@Geekster, this has been [discussed on meta previously](http://meta.cstheory.stackexchange.com/questions/374/re-ask-vs-edit-reopen) and this kind of reposing is fine. As I said before, if you have an issue like this and don't understand why other users and moderators act differently from what you expect please bring it up on the meta (and not in the comments). Since you are unfamiliar with the previous meta discussions about this kind of issues I would suggest that you refrain from posting such strong comments in future.
Kaveh
CC BY-SA 3.0
2012-08-21T14:53:53.903Z
Every user with high enough reputation has a close vote and if they think a question is a duplicate/repost they can use it to close it as such. Their judgments doesn't need to be compatible with yours. If you don't understand their decisions then you can ask for an explanation on [meta] (but don't do so in the comments under questions).
Kaveh
CC BY-SA 3.0
2012-08-21T21:36:50.590Z
@JɛﬀE I'll have you know that I requested closing my question on stats. Hope this will result in some productive answers here.
JohnnyM
CC BY-SA 3.0
2012-08-22T11:07:30.340Z
JohnnyM, I closed your question on stats.SE, per your request. /cc @Kaveh
chl
<ds.algorithms><reference-request><machine-learning><ai.artificial-intel><genetic-algorithms>
Ultimate Jedi Challenge - Multiarmed Bandit / Reinforcment Learning / advanced AI problem
JohnnyM
# Ultimate Jedi Challenge - Multiarmed Bandit / Reinforcment Learning / advanced AI problem

(Asked by: username_0 on 2012-08-15)

(This is an attempt to reformulate [this question](https://stackoverflow.com/questions/11941402/ultimate-jedi-challenge-multiarmed-bandit-reinforcement-learing-advanced-ai) more concisely.)

## Context

You are a Jedi master who wants to prepare a training program (online-algorithm) for his apprentice, "Luke". Luke needs to practice several (10-20) *abilities*. You can train Luke by preparing *challenges*, each connected to one *ability*.

The outcome of each challenge is binary: Luke succeeds (1) or Luke fails (0). If Luke fails a challenge in an ability, you give him a *lecture* that you can assume will improve his chance of succeeding in next challenge in this ability.

You have a limited number (~50) of challenges to use before Luke has to take a test. However, if Luke fails at some challenge during practice you receive extra challenges. The goal of your training program is to maximize the outcome of the *test*. The *test* is a set of (about 20-25) challenges uniformly distributed between abilities.

## Problem definition

Consider a problem of probing a set $P = \{p\_0,...,p\_n\}$ of $N$ independent processes which resemble human learning (practice makes perfect). At each time the program chooses one process $i$ to probe, denoted by the action $U(t)$, and receives an information of the current, **binary** state $S\_i(t)$ of that process. The probability of $S\_i(t)$ = 1 is defined by
$$
p(S\_i(t) = 1) = g\_i(c\_i(t))
$$
Where $g\_i$ is a non-decreasing function and $c\_i(t)$ describes how many times proces $p\_i$ was probed so far. We can assume $g\_i$ ressembles the **learning curve**, but each $g\_i$ can have an arbitraty offset at $t\_0$ ie:
![$g_i$ offset on the learning curve at time $t_0$](https://i.sstatic.net/W0u5t.png)
Knowing that the amount of remaining probing action is given by
$$
h(t+1) = \begin{cases}
h(t)-1\,, &\text{ if $i \in U(t)$ and $S\_i(t) = 1$;} \\
h(t)-1+f(h(t))\,, &\text{ otherwise,}
\end{cases}
$$
where the function $f$ is one of the input variables — propose a *probing policy* which maximizes a testing function $q$ that will evaluate the state of all processes when there are no more remaining probes, namely:
$$q(t\_{stop}) = \sum\_{i = 0}^{N}S\_i(t\_{stop}),$$
where $t\_{stop}$ is such that $h(t\_{stop}) = 0$.

## My ideas of approaching this problem

We can try to model this problem in at least two ways:

1. As a special case of Non-Bayesian Binary Restless Multi-armed Bandit (RMBA) with Non-Identical Arms (some reading [one](http://arxiv.org/abs/1011.4752), [two](http://www-scf.usc.edu/~ygai/papers/Allerton2011.pdf), [three](http://www.isif.org/sites/isif.org/files/journals/2-6075D01.pdf)) meaning :

   * Restless - reward probability evolves over time
   * Non-Bayesian - underlying Markov transitions are not known
   * Non-Identical Arms - each arm is an independent Markov process
   * We would assume that the algorithm receives a reward each time it probes a process that will return 0 (Luke fails a challenge).
   * I would start by adopting some policy similar to $\epsilon$-greedy.
2. As a case for Reinforcement Learning .

   * I'm just starting to familiarize myself with these areas of research so I can't provide any insight here, although according to my initial reading it seems very promising. I will update the question once I learn anything meaningful.

## Question

What would you recommend as the best references for this problem, or closely related problems? I'm interested primarily in approaches which are not just theoretically feasible, but which would be effective in practise.

Can you suggest a policy that would be effective with these constraints? I am especially interested in good ways to update the belief vector.

**Tags:** ds.algorithms, reference-request, machine-learning, ai.artificial-intel, genetic-algorithms

> **Comments:**
> **username_0**: I appreciate the edits improving question quality. I do not appreciate changing the title - its purpose is to attract attention and set up the context.  
> **username_1**: You forgot to specify how S_i(t) is defined.  
> **username_0**: @TsuyoshiIto Done! It was stated in the context but I added it to the technical definition.  
> **username_1**: As a general issue, you should understand that what you need is not a “problem definition in technical terms,” but a precise definition.  Of course, to state a precise definition, you usually need some technical terms, but using technical terms is not a goal.  
> **username_1**: As a specific issue, specifying that S_i(t) is binary does not define what the value of S_i(t) is: it only says that it is either 0 or 1.  If it is chosen randomly, you have to specify the probability distribution.  If it is chosen adversarially, you have to specify what the constraint on the choice is.  With the current formulation, I cannot rule out the possibility that no matter what I do, I receive S_1(t_stop) = … = S_n(t_stop) = 0, completely unrelated to the values of S_i(t) for t<t_stop.  
> **username_2**: @Johnny, I think your title is more like keywords and doesn't state your question. The general advice is to make your question the title. I suggest using the tags in place of the title for listing keywords. (Or you can list them inside the question.)  
> **username_0**: @TsuyoshiIto Thank you for this insight - in general the process should model human learning and it's hard to define it. In simple words you wan't to probe it (train it) enough times for it to start returning 1's. I do have an idea of how to present it but it needs some refinement. I will post it in the afternoon.  
> **username_1**: When revising the question, please also check the following page, which contains useful advice from many people on asking questions about how to model something: http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions.  Such questions can become great questions which connect theoretical computer science to other fields.  But in its current form, I am afraid that your question is an example of the bad scenario which Scott described: _if the only answer to your question you could reasonably expect from a TCS expert is "I dunno," why are you asking it here? :)_  
> **username_3**: I suppose, as a first approximation, $S_i(t)$ is a bernoulli random variable s.t. the  probability of getting one is a function of the number "probes". I.e. we can think of $p_i:\mathbb{N} \rightarrow [0, 1]$, which is a decreasing function, and when $i$ has been probed $x = x_i(t)$ times up to step $t$, $S_i(t) = 1$ w.p. $p_i(x)$. Is this fair?  
> **username_4**: FYI, this question was also crossposted at http://stats.stackexchange.com/questions/34371.  
> **username_0**: @SashoNikolov Yes this seems fair - this is more or less how I was going to describe it! I know I said I will update the question yesterday but my professional duties overwhelmed me in last 2 days. I will extend the question to include a modified version of your proposal tommorow.  
> **username_1**: @Sasho: Why is p_i a decreasing function?  I thought that it should be an increasing function.  (Not that I care much about this question, especially after seeing username_4’s link.)  
> **username_3**: @TsuyoshiIto sure, increasing. i was thinking of $S_i(t)$ as an error indicator, but I guess it's a success indicator. i think it's a potentially interesting  question (but have not thought about it much to make sure it's not trivial or ill-defined) that's not written in the best way. why does username_4's link change anything? crossposting is orthogonal to question quality imo  
> **username_0**: @SashoNikolov We can view it both ways - to be honest it does not change much in my opinion. Also, could you suggest ways to improve this question? I did my best and based the description on common descriptions of Multiarmed Bandit (see references). I will appreciate all comments that will lead to improving this quest. I also have no idea why username_1 thinks crossposting  changes anyting - this question falls into scope of both sites and they do have different readership.  
> **username_3**: @username_0 you have not edited the question to make precise how the distribution of $S_i$ changes with the number of probes (i.e. incorporate my suggestion above or something else). Also, crossposting is discouraged on stachexchange, so please close one of your questions and you can reopen it if the other one yields no answers. I was just saying that crossposting is orthogonal to question quality, but I am not encouraging it!  
> **username_5**: I would like to know why hell did not break loose because this person submitted an extremely similar question after this one got 6 minus votes http://cstheory.stackexchange.com/questions/12290/ultimate-jedi-challenge-multiarmed-bandit-reinforcement-learing-advanced-ai  
> **username_5**: So are we picking and choosing who can re-post a question after it gets so any negative votes instead of encouraging them to revise the first question?  
> **username_0**: @SashoNikolov I've updated the question with the definition of $S_i$ and an initial model of how the probability of $S_i = 1$ is changing overtime. I would appreciate a quick guide how to close the crossposted question - there is nothing in the faq.  
> **username_0**: @Geekster I'll let you know this new question has very little to do with the previous post this is more narrowed down, precise and well defined - if one can publish 2 articles one specific and another with a more broad approach I don't see why the same principle cannot apply to cstheory questions.  
> **username_6**: @Geekster: Hell did not break loose because of the obvious _effort_ the OP put into reformulating his question.  It wasn't just a verbatim repost.  
> **username_6**: @username_0: If you can't close the cross-posted question on stats.SE yourself, flag the question and ask the moderators to close it.  (Also: Don't do that again.)  
> **username_2**: @Geekster, this has been [discussed on meta previously](http://meta.cstheory.stackexchange.com/questions/374/re-ask-vs-edit-reopen) and this kind of reposing is fine. As I said before, if you have an issue like this and don't understand why other users and moderators act differently from what you expect please bring it up on the meta (and not in the comments). Since you are unfamiliar with the previous meta discussions about this kind of issues I would suggest that you refrain from posting such strong comments in future.  
> **username_2**: Every user with high enough reputation has a close vote and if they think a question is a duplicate/repost they can use it to close it as such. Their judgments doesn't need to be compatible with yours. If you don't understand their decisions then you can ask for an explanation on [meta] (but don't do so in the comments under questions).  
> **username_0**: @JɛﬀE I'll have you know that I requested closing my question on stats. Hope this will result in some productive answers here.  
> **username_7**: username_0, I closed your question on stats.SE, per your request. /cc @username_2  

---

## 0 answers

