An optimization apparatus includes: a selection unit that selects, as a correction value, an element having a magnitude equal to or smaller than a predetermined value from among convex hulls of a policy set; an acquisition unit that acquires a result of execution of a second policy executed in a second round, the second round being a round a predetermined round before a first round for executing a first policy that is determined from among the policy set; a calculation unit that calculates an estimated value of a loss vector in the execution of the policy based on the result of the execution and the correction value selected in the second round; an update unit that updates a first probability distribution based on the estimated value; and a determination unit that determines a policy for a next round based on the updated first probability distribution.