The item cold-start problem is inherent to collaborative filtering (CF) recommenders where items and users are represented by vectors in a latent space. It emerges since CF recommenders rely solely on historical user interactions to characterize their item inventory. As a result, an effective serving of new and trendy items to users may be delayed until enough user feedback is received, thus, reducing both users' and content suppliers' satisfaction. To mitigate this problem, many commercial recommenders apply random exploration and devote a small portion of their traffic to explore new items and gather interactions from random users. Alternatively, content or context information is combined into the CF recommender, resulting in a hybrid system. Another hybrid approach is to learn a mapping between the item attribute space and the CF latent feature space, and use it to characterize the new items providing initial estimates for their latent vectors. In this paper, we adopt the attribute-to-feature mapping approach to expedite random exploration of new items and present LearnAROMA - an advanced algorithm for learning the mapping, previously proposed in the context of classification. In particular, LearnAROMA learns a Gaussian distribution over the mapping matrix. Numerical evaluation demonstrates that this learning technique achieves more accurate initial estimates than logistic regression methods. We then consider a random exploration setting, in which new items are further explored as user interactions arrive. To leverage the initial latent vector estimates with the incoming interactions, we propose DynamicBPR - an algorithm for updating the new item latent vectors without retraining the CF model. Numerical evaluation reveals that DynamicBPR achieves similar accuracy as a CF model trained on all the ratings, using 71% less exploring users than conventional random exploration.