Before revision:  In this paper we develop new algorithmic ideas that allow us to obtain a polynomial-time (1 - 1{e})-approximation algorithm (asymptotically and in expectation) for any matroid, and thus allow us to control the (1-1{e})-approximate regret.
After revision:  In this paper we develop new algorithmic ideas that allow us to obtain a polynomial-time (1 - 1{e})-approximation algorithm (asymptotically and in expectation) for any matroid, and thus to control the (1-1{e})-approximate regret.