There is a variant of the secretary problem that assumes a different payoff structure - each secretary has a payoff which is uniformly distributed U(0,A) for unknown A. As I recall, the stopping time is O(sqrt(N)).