An information processing apparatus includes: a selection section for selecting a subset Xt⊆[n] of a set [n] in a certain round t∈[T] with reference to an observation value of an objective function in a round t−1; and an output section for outputting information indicating the subset Xt⊆[n] which has been selected by the selection section, the selection section selecting the subset Xt⊆[n] so that an asymptotic behavior of an expected value of a regret Σt∈[T]ft(Xt)−Σt∈[T]ft(X*), which is expressed using an observation value ft(Xt) of an objective function in each round t∈[T] and a comparative solution X*, is bounded from above by an upper limit value A(Δ,n,C) which depends at least on a gap indicator Δ in a stochastic model and on a corruption indicator C indicating an adversarial corruption of the stochastic model.