4 ms·

Optimal Stopping Problem always confused me, since it seems to assume you’re not aware of a meaningful measure of what an optimal match would be, but aware of w

Optimal Stopping Problem always confused me, since it seems to assume you’re not aware of a meaningful measure of what an optimal match would be, but aware of what the optimal set of potential matches is. For example, say there’s a goose looking for a mate and they only look at geese of the opposite sex, but in fact, that specific goose’s optimal mate type is a black swan. Maybe it’s just me, but at the point you’re able to limit yourself to a type of X then you likely known Y are the attributes that best define it. Am I missing something other than the obvious point that as the selector you aware of a finite set or the spectrum of quality within it, but lack control over the order for which possible candidates are presented for selection?

nighthawk454 4y ago
It's not about optimal matches at all - it's about when to stop looking. The assumption is you don't known the set of potential matches, or the order they come in, or anything really. But there is a deadline for the decision (or a maximum number of attempts). So how to balance making attempts to gather information with committing to a final decision so you don't run out of time? All else being equal, the rule is 1/e. Spend the first 37% of your time/attempts gathering information, then commit to the next option that's better than you've seen. This doesn't guarantee a good match (or even a match!) but probabilistically the strategy is optimal.
- fierro 4y ago
  exactly. The optimal stopping solution maximizes the probability you find the best candidate. That probability ends up being quite low, unfortunately.
- maxminminmax 4y ago
  >but probabilistically the strategy is optimal. For what value function? It is basically never the case that my value function is "all choices other than the optimal are equally bad" -- which is what this rule is based on. As a personal opinion, this drives me up the wall. There is a great problem here, and there is a whole area (several of them, actually!) of applied math dedicated to it (Statistical Decision Theory, Reinforcement Learning, you name it). Instead we get this toy version -- which at best is an oversimplified intro to he subject, and at worst an excuse to bamboozle with math-fairy-dust -- brought out as some kind of rule "to live by". Your algorithm is bad, and you should feel bad.
  - taeric 4y ago
    I'm confused, isn't this literally one of the founding problems to "Statistical Decision Theory"? That is, this may be a simplified version of the problem, but it is a legit problem from that field. And the results being presented here don't disagree with the legit problem, do they? Now, is it a simplification of a simplification? Sure. I'm not clear on why it is as bad as you are putting forth, though.
    - robrenaud 4y ago
      People discuss it as though it has basically any real life applicability, but the assumptions are violated by basically every important real life decision ever. Don't get me wrong, I love algorithms, CS and math and very much liked learning the secretary problem and solution. I just wouldn't think of it as practically useful.
      - taeric 4y ago
        I'm guessing you see/hear this discussed way more than I do, then. :D
bumby 4y ago
I think they address this in a discussion about lacking full information. "We don't have an objective or preexisting sense of what makes for a good or bad applicant; moreover, when we compare two of them we know which of the two is better, but not by how much." (p. 18) They then go on to explain stopping thresholds in the cases when you do have full information.
cjohnson318 4y ago
My understanding of the optimal stopping problem is that you basically take a sample that's approximately N/e, and then you accept the first candidate that exceeds the scores of the members in that sample, or you accept the last candidate, regardless of their score. I think the key thing is that a priori you don't know what the spectrum of quality is in the initial set. You're basing "the bar" on what you've just seen. It's like dating, you might pass on some great people before you realize what the dating pool really looks like.

nighthawk454 4y ago

It's not about optimal matches at all - it's about when to stop looking. The assumption is you don't known the set of potential matches, or the order they come in, or anything really. But there is a deadline for the decision (or a maximum number of attempts). So how to balance making attempts to gather information with committing to a final decision so you don't run out of time? All else being equal, the rule is 1/e. Spend the first 37% of your time/attempts gathering information, then commit to the next option that's better than you've seen. This doesn't guarantee a good match (or even a match!) but probabilistically the strategy is optimal.

fierro 4y ago
exactly. The optimal stopping solution maximizes the probability you find the best candidate. That probability ends up being quite low, unfortunately.
maxminminmax 4y ago
>but probabilistically the strategy is optimal. For what value function? It is basically never the case that my value function is "all choices other than the optimal are equally bad" -- which is what this rule is based on. As a personal opinion, this drives me up the wall. There is a great problem here, and there is a whole area (several of them, actually!) of applied math dedicated to it (Statistical Decision Theory, Reinforcement Learning, you name it). Instead we get this toy version -- which at best is an oversimplified intro to he subject, and at worst an excuse to bamboozle with math-fairy-dust -- brought out as some kind of rule "to live by". Your algorithm is bad, and you should feel bad.
- taeric 4y ago
  I'm confused, isn't this literally one of the founding problems to "Statistical Decision Theory"? That is, this may be a simplified version of the problem, but it is a legit problem from that field. And the results being presented here don't disagree with the legit problem, do they? Now, is it a simplification of a simplification? Sure. I'm not clear on why it is as bad as you are putting forth, though.
  - robrenaud 4y ago
    People discuss it as though it has basically any real life applicability, but the assumptions are violated by basically every important real life decision ever. Don't get me wrong, I love algorithms, CS and math and very much liked learning the secretary problem and solution. I just wouldn't think of it as practically useful.
    - taeric 4y ago
      I'm guessing you see/hear this discussed way more than I do, then. :D

bumby 4y ago

I think they address this in a discussion about lacking full information. "We don't have an objective or preexisting sense of what makes for a good or bad applicant; moreover, when we compare two of them we know which of the two is better, but not by how much." (p. 18) They then go on to explain stopping thresholds in the cases when you do have full information.

cjohnson318 4y ago

My understanding of the optimal stopping problem is that you basically take a sample that's approximately N/e, and then you accept the first candidate that exceeds the scores of the members in that sample, or you accept the last candidate, regardless of their score. I think the key thing is that a priori you don't know what the spectrum of quality is in the initial set. You're basing "the bar" on what you've just seen. It's like dating, you might pass on some great people before you realize what the dating pool really looks like.